Some Undecidability Results For Finitely Generated Thue Congruences On A Two-Letter Alphabet

Abstract

Following the course set by A. Markov (1951), S. Adjan (1958), and M. Rabin (1958), C. Ó'Dúnlaing (1983) has shown that certain properties of finitely generated Thue congruences are undecidable in general. Here we prove that many of these undecidability results remain valid even when only finitely generated Thue congruences on a fixed two-letter alphabet Σ₂ are considered. In contrast to a construction given by P. Schupp (1976) which applies to groups only, we use a modified version of a technical lemma from A. Markov's original paper. Based on this technical result we can carry the result of A. Sattler-Klein (1996), which says that certain Markov properties remain undecidable even when they are restricted to finitely generated Thue congruences that are decidable, over to the alphabet Σ₂.