Undecidable properties on length-two string rewriting systems

DOI10.1016/J.ENTCS.2008.03.053MaRDI QIDQ2873677zbMATH OpenOpenAlexFDO

Authors Masahiko Sakai, Yi Wang

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

confluenceleft-most terminationlength-two string rewriting systemrewriting systemright-most termination

Mathematics Subject Classification ID

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

Recommendations

• On the property of preserving regularity for string-rewriting systems
• scientific article; zbMATH DE number 1638661
• New Undecidability Results for Properties of Term Rewrite Systems
• Some properties of finite special string-rewriting systems
• scientific article; zbMATH DE number 4060699

Cites work

• A variant of a recursively unsolvable problem
• Automated Deduction – CADE-20
• Computer Science Logic
• Decidability of Termination for Semi-constructor TRSs, Left-Linear Shallow TRSs and Related Systems
• Decision problems for semi-Thue systems with a few rules
• scientific article; zbMATH DE number 1638661 (Why is no real title available?)
• scientific article; zbMATH DE number 3729436 (Why is no real title available?)
• scientific article; zbMATH DE number 1962804 (Why is no real title available?)
• scientific article; zbMATH DE number 3299786 (Why is no real title available?)
• Reachability and confluence are undecidable for flat term rewriting systems
• Relative undecidability in term rewriting. I: The termination hierarchy
• Relative undecidability in term rewriting. II: The confluence hierarchy
• Simulation of Turing machines by a regular rewrite rule
• Termination of term rewriting: Interpretation and type elimination
• The Church-Rosser property for ground term-rewriting systems is decidable
• The Confluence Problem for Flat TRSs

Cited in

(5)

• scientific article; zbMATH DE number 1638661 (Why is no real title available?)
• Weakly-non-overlapping non-collapsing shallow term rewriting systems are confluent
• On the property of preserving regularity for string-rewriting systems
• New Undecidability Results for Properties of Term Rewrite Systems
• Undecidable properties of flat term rewrite systems

This page was built for publication: Undecidable properties on length-two string rewriting systems

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