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 条
12345