On fixed points of rational transductions

被引：0

作者：

Halava, Vesa ^{[1
,2
]}

Harju, Tero ^{[1
]}

Sahla, Esa ^{[1
]}

机构：

[1] Univ Turku, Dept Math & Stat, Turku, Finland

[2] Univ Turku, Turku Complex Syst Inst, Dept Math & Stat, Turku, Finland

来源：

THEORETICAL COMPUTER SCIENCE | 2018年 / 732卷

关键词：

Fixed points; Rational transductions; Post correspondence problem; Injective PCP; Decidability; MORPHISMS;

D O I：

10.1016/j.tcs.2018.04.030

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that it is undecidable whether or not an injective rational function (realized by a finite transducer) f : A* -> A* has a fixed point. The proof applies undecidability of the Post's Correspondence Problem for injective morphisms. As a corollary we obtain that the existence of a fixed point of injective computable functions is undecidable. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：85 / 88

页数：4

共 50 条

[41] On a problem of common approximate fixed points
Wisnicki, A
NONLINEAR ANALYSIS-THEORY METHODS & APPLICATIONS, 2003, 52 (06) : 1637 - 1643
[42] An expansion of Basic Logic with fixed points
Spada, Luca
SOFT COMPUTING, 2017, 21 (01) : 29 - 37
[43] On Fixed Points of Linguistic Dynamic Systems
王飞跃
系统仿真学报, 2002, (11) : 1479 - 1485
[44] Fixed Points for Cubic Coquaternionic Maps
Falcao, Maria Irene
Miranda, Fernando
Severino, Ricardo
Soares, Maria Joana
COMPUTATIONAL SCIENCE AND ITS APPLICATIONS, ICCSA 2022 WORKSHOPS, PT I, 2022, 13377 : 450 - 465
[45] Probabilistic truth approximation and fixed points
Atkinson, David
Peijnenburg, Jeanne
SYNTHESE, 2021, 199 (1-2) : 4195 - 4216
[46] Fixed points of univalent functions II
Schmieder, Gerald
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2006, 134 (12) : 3605 - 3611
[47] Fixed points and stability of a nonconvolution equation
Burton, TA
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2004, 132 (12) : 3679 - 3687
[48] An expansion of Basic Logic with fixed points
Luca Spada
Soft Computing, 2017, 21 : 29 - 37
[49] Fixed Points in Distance Recurrence Formulas
Thomas, Federico
ADVANCES IN ROBOT KINEMATICS 2024, ARK 2024, 2024, 31 : 399 - 406
[50] FIXED-POINTS OF INCREASING FUNCTIONS
HOARE, CAR
INFORMATION PROCESSING LETTERS, 1990, 34 (03) : 111 - 112

← 1 2 3 4 5 →