Uniqueness of Normal Forms for Shallow Term Rewrite Systems

DOI10.1145/3060144zbMath1367.68149arXiv1607.00431OpenAlexW2962928105MaRDI QIDQ5278216

Nicholas R. Radcliffe, Rakesh M. Verma, Luis F. T. Moraes

Publication date: 13 July 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.00431

zbMATH Keywords

undecidabilitydecidabilityterm rewrite systemsuniqueness of normal formsflat rewrite systemsshallow rewrite systems

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems
• Undecidable properties of flat term rewrite systems
• Syntacticness, cycle-syntacticness and shallow theories
• Deciding confluence of certain term rewriting systems in polynomial time
• 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
• Variations on the Common Subexpression Problem
• New Undecidability Results for Properties of Term Rewrite Systems
• The Confluence Problem for Flat TRSs

This page was built for publication: Uniqueness of Normal Forms for Shallow Term Rewrite Systems