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

Halava, Vesa; Harju, Tero

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].

MSC:

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