Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule (Q1107523)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule |
scientific article |
Statements
Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule (English)
0 references
1988
0 references
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.
0 references
decidability
0 references
Thue system
0 references
preperfectness
0 references
confluence modulo partial commutativity
0 references