Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule (Q1107523): Difference between revisions

As shown by \textit{P. Narendran} and \textit{R. McNaughton} [Theor. Comput. Sci. 31, 165-174 (1984; Zbl 0545.03022)] it is undecidable in general whether a finite Thue system is preperfect. Here it is shown that this problem remains undecidable even if the Thue systems under consideration contain only left-reducing rules plus a single length-preserving rule, which is a commutation rule of the form (ab,ba), where a and b are distinct letters. In particular, this implies that it is undecidable in general whether or not a finite Thue system containing only length- reducing rules is confluent modulo a partial commutativity relation.