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

DOI10.1016/0020-0190(88)90049-XMaRDI QIDQ1107523zbMATH OpenFDO

Authors Paliath Narendran, Friedrich Otto

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90049-X

zbMATH Keywords

confluence modulo partial commutativitydecidabilitypreperfectnessThue system

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03)

Review text

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.

Recommendations

• The undecidability of the preperfectness of Thue systems
• On reduced thue systems
• Some undecidable termination problems for semi-Thue systems
• scientific article; zbMATH DE number 671957
• On the regular equivalence problem for regular Thue systems

Cites work

• An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
• Completion of a Set of Rules Modulo a Set of Equations
• Confluent and Other Types of Thue Systems
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• scientific article; zbMATH DE number 4030960 (Why is no real title available?)
• scientific article; zbMATH DE number 3756462 (Why is no real title available?)
• Rewriting systems and word problems in a free partially commutative monoid
• Testing for the Church-Rosser property
• The undecidability of the preperfectness of Thue systems

Cited in

(12)

• On the Knuth-Bendix completion for concurrent processes
• On deciding confluence of finite string-rewriting systems modulo partial commutativity
• Confluence problems for trace rewriting systems
• WORD EQUATIONS OVER GRAPH PRODUCTS
• On confluence of one-rule trace-rewriting systems
• On confluence versus strong confluence for one-rule trace-rewriting systems
• Word problems over traces which are solvable in linear time
• One-rule trace-rewriting systems and confluence
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• The undecidability of the preperfectness of Thue systems
• A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems
• Word problems over traces which are solvable in linear time

This page was built for publication: Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107523)