On the dual post correspondence problem
Joel Day
Daniel Reidenbach
Johannes C. Schneider
2134/14013
https://repository.lboro.ac.uk/articles/conference_contribution/On_the_dual_post_correspondence_problem/9404741
The Dual Post Correspondence Problem asks whether, for a given word α, there exists a pair of distinct morphisms σ, τ, one of which needs to be non-periodic, such that σ(α) = τ(α) is satisfied. This problem is important for the research on equality sets, which are a vital concept in the theory of computation, as it helps to identify words that are in trivial equality sets only. Little is known about the Dual PCP for words α over larger than binary alphabets. In the present paper, we address this question in a way that simplifies the usual method, which means that we can reduce the intricacy of the word equations involved in dealing with the Dual PCP. Our approach yields large sets of words for which there exists a solution to the Dual PCP as well as examples of words over arbitrary alphabets for which such a solution does not exist.
2014-01-23 14:36:18
Morphisms
Equality sets
Dual Post Correspondence Problem
Periodicity forcing sets
Ambiguity of morphisms
Information and Computing Sciences not elsewhere classified