Abstract:Deciding whether a given word is an equality word of two nonperiodic morphisms is also known as the dual Post correspondence problem. Although the problem is decidable, there is no practical decision algorithm. Already in the binary case, the classification is a large project dating back to 1980s. In this paper we give a full classification of binary equality words in which one of the letters has two occurrences.
Keywords: equality languages; dual Post correspondence problem; periodicity forcing
DOI: DOI 10.14712/1213-7243.2015.247
AMS Subject Classification: 68R15