Undecidable properties of flat term rewrite systems

DOI10.1007/s00200-009-0097-1zbMath1187.68274OpenAlexW2095909184MaRDI QIDQ734041

Guillem Godoy, Hugo Hernández

Publication date: 19 October 2009

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-0097-1

zbMATH Keywords

undecidabilityterm rewritingsyntactic restrictions

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (3)

Uniqueness of Normal Forms for Shallow Term Rewrite Systems ⋮ Normalization properties for shallow TRS and innermost rewriting ⋮ Unique Normalization for Shallow TRS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reachability and confluence are undecidable for flat term rewriting systems
• Decidability for left-linear growing term rewriting systems.
• Decidability of Termination for Semi-constructor TRSs, Left-Linear Shallow TRSs and Related Systems
• On the Normalization and Unique Normalization Properties of Term Rewrite Systems
• Term Rewriting and All That
• The Confluence Problem for Flat TRSs
• Automated Reasoning
• Computer Science Logic
• Termination of Rewriting with Right-Flat Rules

This page was built for publication: Undecidable properties of flat term rewrite systems