A1 Refereed original research article in a scientific journal
On fixed points of rational transductions
Authors: Vesa Halava, Tero Harju, Esa Sahla
Publisher: Elsevier
Publication year: 2018
Journal:Theoretical Computer Science
Journal name in sourceTHEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 732
First page : 85
Last page: 88
Number of pages: 4
ISSN: 0304-3975
eISSN: 1879-2294
DOI: https://doi.org/10.1016/j.tcs.2018.04.030
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.
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.
UTU Research Portal