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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Une généralisation des ensembles de Dyck
• Confluent and Other Types of Thue Systems
• Testing for the Church-Rosser property
• Infinite regular Thue systems
• Homogeneous Thue systems and the Church-Rosser property

Cited In (14)

• Title not available (Why is that?)
• On deciding confluence of finite string-rewriting systems modulo partial commutativity
• The undecidability of self-embedding for finite semi-Thue and Thue systems
• Thue systems as rewriting systems
• Some undecidable termination problems for semi-Thue systems
• 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
• Title not available (Why is that?)
• Trace monoids with some invertible generators: Two decision problems
• Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group
• 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
• On confluence of one-rule trace-rewriting systems
• On the regular equivalence problem for regular 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)