Normalization properties for shallow TRS and innermost rewriting

DOI10.1007/S00200-009-0118-0zbMath1184.68298OpenAlexW2087323415MaRDI QIDQ964737

Guillem Godoy

Publication date: 20 April 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-009-0118-0

zbMATH Keywords

decidabilityterm rewritingsyntactic restrictionsinnermost rewriting

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Undecidable properties of flat term rewrite systems
• Deterministic tree pushdown automata and monadic tree rewriting systems
• Linear generalized semi-monadic rewrite systems effectively preserve recognizability
• Bottom-up tree pushdown automata: Classification and connection with rewrite systems
• Decidability for left-linear growing term rewriting systems.
• Deciding confluence of certain term rewriting systems in polynomial time
• On the Normalization and Unique Normalization Properties of Term Rewrite Systems
• Term Rewriting and All That
• RIGID REACHABILITY, THE NON-SYMMETRIC FORM OF RIGID E-UNIFICATION
• Bottom-Up Rewriting Is Inverse Recognizability Preserving
• Innermost-Reachability and Innermost-Joinability Are Decidable for Shallow Term Rewrite Systems

This page was built for publication: Normalization properties for shallow TRS and innermost rewriting