A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems
From MaRDI portal
Publication:613611
DOI10.1007/s00200-010-0133-1zbMath1211.68227OpenAlexW2006460851MaRDI QIDQ613611
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
basic properties of rewrite systemslinear shallow rewrite systemsterm rewrite systemsuniqueness of normal forms
Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42) Word problems, etc. in computability and recursion theory (03D40)
Related Items (3)
Uniqueness of Normal Forms for Shallow Term Rewrite Systems ⋮ New Undecidability Results for Properties of Term Rewrite Systems ⋮ Unique Normalization for Shallow TRS
Cites Work
- Unnamed Item
- Decidability and complexity analysis by basic paramodulation
- Sequentiality, monadic second-order logic and tree automata.
- Deciding confluence of certain term rewriting systems in polynomial time
- 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
- Automated Deduction – CADE-20
This page was built for publication: A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems