A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On fixed points of rational transductions
Tekijät: Vesa Halava, Tero Harju, Esa Sahla
Kustantaja: Elsevier
Julkaisuvuosi: 2018
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 732
Aloitussivu: 85
Lopetussivu: 88
Sivujen määrä: 4
ISSN: 0304-3975
eISSN: 1879-2294
DOI: https://doi.org/10.1016/j.tcs.2018.04.030
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali