Levels of undecidability in rewriting

DOI10.1016/j.ic.2010.09.003zbMath1210.68064OpenAlexW2128968863MaRDI QIDQ627134

Jörg Endrullis, Jakob Grue Simonsen, Hans Zantema, Herman Geuvers

Publication date: 21 February 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2010.09.003

zbMATH Keywords

classificationhierarchyfirst order term rewriting systemsproperties related to confluenceproperties related to normalization

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42)

Related Items

Termination of Cycle Rewriting by Transformation and Matrix Interpretation ⋮ Transducer degrees: atoms, infima and suprema ⋮ Highlights in infinitary rewriting and lambda calculus ⋮ Decreasing diagrams with two labels are complete for confluence of countable systems ⋮ Unnamed Item ⋮ On the complexity of stream equality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• Models of computation. An introduction to computability theory
• Reachability and confluence are undecidable for flat term rewriting systems
• Conditional rewrite rules
• Conditional rewrite rules: Confluence and termination
• Termination of term rewriting: Interpretation and type elimination
• Simple termination is difficult
• Omega-termination is undecidable for totally terminating term rewriting systems
• Decidability for left-linear growing term rewriting systems.
• Relative undecidability in term rewriting. I: The termination hierarchy
• Relative undecidability in term rewriting. II: The confluence hierarchy
• Total termination of term rewriting is undecidable
• Termination of term rewriting using dependency pairs
• Arithmetical Predicates and Function Quantifiers
• Hierarchies of number-theoretic predicates
• THE WORD PROBLEM
• Normalization of Infinite Terms
• The $\Pi^0_2$ -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity)
• Degrees of Undecidability in Term Rewriting
• Undecidable properties of syntactic theories
• Decidable approximations of term rewriting systems
• A new decidability technique for ground term rewriting systems with applications
• Strong Computability and Variants of the Uniform Halting Problem
• Logic for Programming, Artificial Intelligence, and Reasoning
• Recursive Predicates and Quantifiers