Charles Explorer logo
🇬🇧

Binary equality words with two b's

Publication at Faculty of Mathematics and Physics |
2018

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.