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

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4064974
Language Label Description Also known as
default for all languages
No label defined
    English
    Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
    scientific article; zbMATH DE number 4064974

      Statements

      Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule (English)
      0 references
      0 references
      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
      0 references

      Identifiers