A1 Refereed original research article in a scientific journal
On bi-infinite and conjugate post correspondence problems
Authors: Finkel Olivier, Halava Vesa, Harju Tero, Sahla Esa
Publisher: EDP Sciences
Publication year: 2023
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Journal name in source: RAIRO - Theoretical Informatics and Applications
Article number: 7
Volume: 57
ISSN: 2804-7346
eISSN: 1290-385X
DOI: https://doi.org/10.1051/ita/2023008
Web address : https://doi.org/10.1051/ita/2023008
Self-archived copy’s web address: 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.
Downloadable publication This is an electronic reprint of the original article. |  |
