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

DOI10.1007/s00200-010-0133-1zbMath1211.68227MaRDI QIDQ613611

Rakesh M. Verma, Julian Zinn

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 systems; linear shallow rewrite systems; term rewrite systems; uniqueness of normal forms

Mathematics Subject Classification ID

03B25: Decidability of theories and sets of sentences

68Q42: Grammars and rewriting systems

03D40: Word problems, etc. in computability and recursion theory

Related Items

New Undecidability Results for Properties of Term Rewrite Systems, Uniqueness of Normal Forms for Shallow 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