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

共 10 条

[1]

[Anonymous], 1997, Handbook of formal languages

[2]

[Anonymous], 1979, Transductions and context-free languages

[3]

Culik K., 1994, Results and Trends in Theoretical Computer Science. Colloquium in Honor of Arto Salomaa. Proceedings, P85

[4]

Karhumäki J, 2010, DISCRETE MATH THEOR, V12, P9

[5]

LATTEUX M, 1983, LECT NOTES COMPUT SC, V154, P420

[6]

Lecerf M. Y., 1963, COMPTES RENDUS, V257, P2940

[7] A VARIANT OF A RECURSIVELY UNSOLVABLE PROBLEM [J].

POST, EL .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (04) :264-268

[8]

Ruohonen K., 1985, Elektronische Informationsverarbeitung und Kybernetik (EIK), V21, P579

[9]

Sakarovitch J., 2009, Elements of automata theory

[10]

Salomaa A., 1973, Formal Languages

← 1 →