The undecidability of the preperfectness of Thue systems

DOI10.1016/0304-3975(84)90133-6MaRDI QIDQ797574zbMATH OpenOpenAlexFDO

Authors Paliath Narendran, Robert McNaughton

Publication date 1984

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(84)90133-6

zbMATH Keywords

almost-confluent systemsChurch-Rosser systemsemptiness problem for deterministic linear-bounded automatamonoidspreperfect systemsstring replacement systemsThue systems

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Automata and formal grammars in connection with logical questions (03D05) Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40)

Review text

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).

Recommendations

• Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
• The undecidability of self-embedding for finite semi-Thue and Thue systems
• Some undecidability results for non-monadic Church-Rosser Thue systems
• Some undecidable termination problems for semi-Thue systems
• On a method for proving exact bounds on derivational complexity in Thue systems
• Decidability and undecidability of theories with a predicate for the primes
• The undecidability of k-provability
• scientific article; zbMATH DE number 4187789
• A finite Thue system with decidable word problem and without equivalent finite canonical system

Cites work

• Confluent and Other Types of Thue Systems
• Homogeneous Thue systems and the Church-Rosser property
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3073037 (Why is no real title available?)
• Infinite regular Thue systems
• Testing for the Church-Rosser property
• Une généralisation des ensembles de Dyck

Cited in

(14)

• On the regular equivalence problem for regular Thue systems
• The undecidability of self-embedding for finite semi-Thue and Thue systems
• Thue systems as rewriting systems
• Rewriting systems and word problems in a free partially commutative monoid
• Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
• The word problem for free partially commutative groups
• Trace monoids with some invertible generators: Two decision problems
• On deciding confluence of finite string-rewriting systems modulo partial commutativity
• scientific article; zbMATH DE number 671957 (Why is no real title available?)
• scientific article; zbMATH DE number 1051238 (Why is no real title available?)
• On confluence of one-rule trace-rewriting systems
• Some undecidable termination problems for semi-Thue systems
• Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group
• A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems

This page was built for publication: The undecidability of the preperfectness of Thue systems

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