A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On bi-infinite and conjugate post correspondence problems
Tekijät: Finkel Olivier, Halava Vesa, Harju Tero, Sahla Esa
Kustantaja: EDP Sciences
Julkaisuvuosi: 2023
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Tietokannassa oleva lehden nimi: RAIRO - Theoretical Informatics and Applications
Artikkelin numero: 7
Vuosikerta: 57
ISSN: 2804-7346
eISSN: 1290-385X
DOI: https://doi.org/10.1051/ita/2023008
Verkko-osoite: https://doi.org/10.1051/ita/2023008
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/181953141
We study two modifications of the Post Correspondence Problem (PCP), namely (1) the bi-infinite version, where it is asked whether there exists a bi-infinite word such that two given morphisms agree on it, and (2) the conjugate version, where we require the images of a solution for two given morphisms are conjugates of each other. For the conjugate PCP we give an undecidability proof by reducing it to the word problem for a special type of semi-Thue systems and for the bi-infinite PCP we give a simple argument that it is in the class Σ20 of the arithmetical hierarchy.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
