Unique Normalization for Shallow TRS

DOI10.1007/978-3-642-02348-4_5MaRDI QIDQ3636819zbMATH OpenOpenAlexFDO

Authors Guillem Godoy, Florent Jacquemard

Publication date 30 June 2009

Published in Rewriting Techniques and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02348-4_5

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• On the Normalization and Unique Normalization Properties of Term Rewrite Systems
• Normalization properties for shallow TRS and innermost rewriting
• Uniqueness of normal forms for shallow term rewrite systems
• Uniqueness of normal forms is decidable for shallow term rewrite systems
• A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems

Cites work

• A new decidability technique for ground term rewriting systems with applications
• A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems
• Automated Reasoning
• Computer Science Logic
• Decidability for left-linear growing term rewriting systems.
• Decidability of Termination for Semi-constructor TRSs, Left-Linear Shallow TRSs and Related Systems
• Deterministic tree pushdown automata and monadic tree rewriting systems
• Ground reducibility is EXPTIME-complete
• scientific article; zbMATH DE number 1615242 (Why is no real title available?)
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• On the Normalization and Unique Normalization Properties of Term Rewrite Systems
• Reachability and confluence are undecidable for flat term rewriting systems
• Term Rewriting and All That
• Termination of Rewriting with Right-Flat Rules
• The Confluence Problem for Flat TRSs
• Undecidable properties of flat term rewrite systems

Cited in

(7)

• Some undecidable approximations of TRSs
• Uniqueness of normal forms is decidable for shallow term rewrite systems
• Deciding confluence and normal form properties of ground term rewrite systems efficiently
• Uniqueness of normal forms for shallow term rewrite systems
• Non--overlapping TRSs are UN
• A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems
• Tail reduction free term rewriting systems revisited

This page was built for publication: Unique Normalization for Shallow TRS

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