The undecidability of the preperfectness of Thue systems

DOI10.1016/0304-3975(84)90133-6zbMATH Open0545.03022OpenAlexW2027868924MaRDI QIDQ797574FDOQ797574

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

monoidsThue systemsalmost-confluent systemsChurch-Rosser systemsemptiness problem for deterministic linear-bounded automatapreperfect systemsstring replacement systems

Mathematics Subject Classification ID

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

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

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

Cited in

(14)

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

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)