Undecidable properties of flat term rewrite systems

DOI10.1007/S00200-009-0097-1MaRDI QIDQ734041zbMATH OpenOpenAlexFDO

Authors 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

syntactic restrictionsterm rewritingundecidability

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Review text

Reachability, joinability, termination or strong normalization, confluence, weak normalization, and unique normalization are some fundamental properties of term rewrite systems (TRS) that are known to be undecidable in general. Their decidablity has been investigated for some particular classes. In this paper, the authors give new simple proofs for the undecidability of reachability, joinability, and confluence for flat TRS. They also give proofs for the undecidability of weak and unique normalizations for flat TRS.

Recommendations

• Reachability and confluence are undecidable for flat term rewriting systems
• New Undecidability Results for Properties of Term Rewrite Systems
• Undecidable properties on length-two string rewriting systems
• scientific article; zbMATH DE number 1086665
• Degrees of Undecidability in Term Rewriting
• The undecidability of self-embedding for term rewriting systems
• Relative undecidability in term rewriting. I: The termination hierarchy
• Total termination of term rewriting is undecidable
• scientific article; zbMATH DE number 3481859
• Undecidable properties of deterministic top-down tree transducers

Cites work

• 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
• scientific article; zbMATH DE number 1615242 (Why is no real title available?)
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 1962804 (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

Cited in

(7)

• Reachability and confluence are undecidable for flat term rewriting systems
• Unique Normalization for Shallow TRS
• Uniqueness of normal forms for shallow term rewrite systems
• The Confluence Problem for Flat TRSs
• Tail reduction free term rewriting systems revisited
• The reachability and related decision problems for monadic and semi-constructor TRSs
• Normalization properties for shallow TRS and innermost rewriting

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

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