A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems

DOI10.1007/S00200-010-0133-1MaRDI QIDQ613611zbMATHOpenAlexFDO

Authors Julian Zinn, Rakesh M. Verma

Publication date 21 December 2010

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00200-010-0133-1

zbMATH Keywords

basic properties of rewrite systemslinear shallow rewrite systemsterm rewrite systemsuniqueness of normal forms

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Decidability of theories and sets of sentences (03B25) Word problems, etc. in computability and recursion theory (03D40)

Recommendations

• Uniqueness of normal forms for shallow term rewrite systems
• Uniqueness of normal forms is decidable for shallow term rewrite systems
• Complexity of Normal Form Properties and Reductions for Term Rewriting Problems Complexity of Normal Form Properties and Reductions for Term Rewriting Problems
• Unique Normalization for Shallow TRS
• scientific article; zbMATH DE number 1962804

Cites work

• Algorithms and reductions for rewriting problems
• Automated Deduction – CADE-20
• Complexity of Normal Form Properties and Reductions for Term Rewriting Problems Complexity of Normal Form Properties and Reductions for Term Rewriting Problems
• Decidability and complexity analysis by basic paramodulation
• Deciding confluence of certain term rewriting systems in polynomial time
• Sequentiality, monadic second-order logic and tree automata.
• Unique Normalization for Shallow TRS

Cited in

(5)

• New Undecidability Results for Properties of Term Rewrite Systems
• Uniqueness of normal forms is decidable for shallow term rewrite systems
• Complexity of Normal Form Properties and Reductions for Term Rewriting Problems Complexity of Normal Form Properties and Reductions for Term Rewriting Problems
• Unique Normalization for Shallow TRS
• Uniqueness of normal forms for shallow term rewrite systems

This page was built for publication: A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems

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