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

Article type: Research Article

Authors: Madlener, Klaus | Otto, Friedrich

Affiliations: Fachbereich Informatik, Universität Kaiserslautern, D-67653 Kaiserslautern, Germany. [email protected] | Fachbereich Mathematik/Informatik, Universität Kassel, D-34109 Kassel, Germany. [email protected]

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 Σ2 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 Σ2.

Keywords: Thue congruence, finitely presented monoid, Markov property, two-letter alphabet

DOI: 10.3233/FI-1997-30103

Journal: Fundamenta Informaticae, vol. 30, no. 1, pp. 31-44, 1997