Levels of undecidability in rewriting

DOI10.1016/j.ic.2010.09.003zbMath1210.68064MaRDI 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

classification; hierarchy; first order term rewriting systems; properties related to confluence; properties related to normalization

Mathematics Subject Classification ID

03D35: Undecidability and degrees of sets of sentences

68Q42: Grammars and rewriting systems

Related Items

Highlights in infinitary rewriting and lambda calculus, On the complexity of stream equality, Unnamed Item

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item