The undecidability of the preperfectness of Thue systems (Q797574): Difference between revisions

Thue systems are string replacement systems that present monoids. Since the word problem for them was proved to be undecidable by Post and Markov in the 1940's, there has been some interest in developing conditions under which the word problem is decidable. A hierarchy of three has been defined: Church-Rosser systems are properly included in almost-confluent systems, which are properly included in preperfect systems. At present it is possible to decide whether a finite Thue system is almost-confluent or Church-Rosser, but testing for preperfectness has been an open problem for years. Here we prove that it is undecidable, by reducing it to the emptiness problem for deterministic linear-bounded automata (DLBA's).