Undecidable Properties on Length-Two String Rewriting Systems

DOI10.1016/j.entcs.2008.03.053zbMath1279.68118MaRDI 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

confluence; rewriting system; left-most termination; length-two string rewriting system; right-most termination

Mathematics Subject Classification ID

03B25: Decidability of theories and sets of sentences

68Q42: Grammars and rewriting systems

Related Items

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