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

### 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
Full Text: