A1 Journal article – refereed
On fixed points of rational transductions




List of Authors: Vesa Halava, Tero Harju, Esa Sahla
Publisher: Elsevier
Publication year: 2018
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume number: 732
Number of pages: 4
ISSN: 0304-3975
eISSN: 1879-2294

Abstract
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.

Last updated on 2019-20-07 at 05:42