Undecidable Properties on Length-Two String Rewriting Systems

DOI10.1016/j.entcs.2008.03.053zbMath1279.68118OpenAlexW2158605963MaRDI QIDQ2873677

Yi Wang, Masahiko Sakai

Publication date: 24 January 2014

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.entcs.2008.03.053

zbMATH Keywords

confluencerewriting systemleft-most terminationlength-two string rewriting systemright-most termination

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42)

Related Items (1)

Weakly-non-overlapping non-collapsing shallow term rewriting systems are confluent

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reachability and confluence are undecidable for flat term rewriting systems
• The Church-Rosser property for ground term-rewriting systems is decidable
• Simulation of Turing machines by a regular rewrite rule
• Termination of term rewriting: Interpretation and type elimination
• Decision problems for semi-Thue systems with a few rules
• Relative undecidability in term rewriting. I: The termination hierarchy
• Relative undecidability in term rewriting. II: The confluence hierarchy
• Decidability of Termination for Semi-constructor TRSs, Left-Linear Shallow TRSs and Related Systems
• The Confluence Problem for Flat TRSs
• Computer Science Logic
• Automated Deduction – CADE-20
• A variant of a recursively unsolvable problem

This page was built for publication: Undecidable Properties on Length-Two String Rewriting Systems