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 条
  • [1] Fixed points of rational functions satisfying the Carlitz property
    Kaitlyn Chubb
    Daniel Panario
    Qiang Wang
    Applicable Algebra in Engineering, Communication and Computing, 2019, 30 : 417 - 439
  • [2] Fixed points of rational functions satisfying the Carlitz property
    Chubb, Kaitlyn
    Panario, Daniel
    Wang, Qiang
    APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 2019, 30 (05) : 417 - 439
  • [3] FAREY GRAPH AND RATIONAL FIXED POINTS OF THE EXTENDED MODULAR GROUP
    Dem, Bilal
    Karatas, Mustafa
    COMMUNICATIONS FACULTY OF SCIENCES UNIVERSITY OF ANKARA-SERIES A1 MATHEMATICS AND STATISTICS, 2022, 71 (04): : 1029 - 1043
  • [4] Closure under union and composition of iterated rational transductions
    Simplot, D
    Terlutte, A
    RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 2000, 34 (03): : 183 - 212
  • [5] Fixed points of generalized rational (α, β, Z)-contraction mappings under simulation functions
    Stephen, Thounaojam
    Rohen, Yumnam
    JOURNAL OF MATHEMATICS AND COMPUTER SCIENCE-JMCS, 2022, 24 (04): : 345 - 357
  • [6] Fixed points and random fixed points for α-Lipschitzian maps
    O'Regan, D
    NONLINEAR ANALYSIS-THEORY METHODS & APPLICATIONS, 1999, 37 (04) : 537 - 544
  • [7] FIXED POINTS AND COMMON FIXED POINTS OF MAPPINGS ON CAT(0) SPACES
    Asadi, Mehdi
    FIXED POINT THEORY, 2013, 14 (01): : 29 - 38
  • [8] On a conjecture about finite fixed points of morphisms
    Levé, F
    Richomme, G
    THEORETICAL COMPUTER SCIENCE, 2005, 339 (01) : 103 - 128
  • [9] Incompleteness and fixed points
    Sacchetti, L
    MATHEMATICAL LOGIC QUARTERLY, 2002, 48 (01) : 15 - 28
  • [10] The lempel-ziv complexity of fixed points of morphisms
    Constantinescu, Sorin
    Ilie, Lucian
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (02) : 466 - 481
12345