A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems
DOI10.1007/S00200-010-0133-1zbMATH Open1211.68227OpenAlexW2006460851MaRDI QIDQ613611FDOQ613611
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
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
basic properties of rewrite systemslinear shallow rewrite systemsterm rewrite systemsuniqueness of normal forms
Grammars and rewriting systems (68Q42) Decidability of theories and sets of sentences (03B25) Word problems, etc. in computability and recursion theory (03D40)
Cites Work
- Deciding confluence of certain term rewriting systems in polynomial time
- Algorithms and reductions for rewriting problems
- Decidability and complexity analysis by basic paramodulation
- Sequentiality, monadic second-order logic and tree automata.
- 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
Cited In (5)
- 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 is decidable for shallow term rewrite systems
- Uniqueness of normal forms for shallow term rewrite systems
- New Undecidability Results for Properties of 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)
