Infinite solutions of marked Post correspondence problem. (English) Zbl 1060.03068

Brauer, Wilfried (ed.) et al., Formal and natural computing. Essays dedicated to Grzegorz Rozenberg. Berlin: Springer (ISBN 3-540-43190-X). Lect. Notes Comput. Sci. 2300, 57-68 (2002).
Summary: In an instance of the Post Correspondence Problem we are given two morphisms \(h,g\colon A^*\to B^*\). Here we prove that if the morphisms are marked, then it is decidable whether the instance has an infinite solution, i.e., whether or not there exists an infinite word \(\omega\) such that \(h\) and \(g\) are comparable for all prefixes of \(\omega\). This problem is known to be undecidable in general for the Post Correspondence Problem.
For the entire collection see [Zbl 0989.00070].


03D40 Word problems, etc. in computability and recursion theory
03D03 Thue and Post systems, etc.
03B25 Decidability of theories and sets of sentences
68Q45 Formal languages and automata
Full Text: Link