Degrees of Undecidability in Term Rewriting

DOI10.1007/978-3-642-04027-6_20zbMath1257.68093OpenAlexW2119851779MaRDI QIDQ3644753

Jörg Endrullis, Herman Geuvers, Hans Zantema

Publication date: 12 November 2009

Published in: Computer Science Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04027-6_20

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Hierarchies of computability and definability (03D55)

Related Items

Highlights in infinitary rewriting and lambda calculus ⋮ Levels of undecidability in rewriting ⋮ Least Upper Bounds on the Size of Church-Rosser Diagrams in Term Rewriting and λ-Calculus ⋮ Behavioral Rewrite Systems and Behavioral Productivity ⋮ Regaining cut admissibility in deduction modulo using abstract completion ⋮ Complexity of Fractran and Productivity ⋮ Unnamed Item ⋮ Degrees of Undecidability in Term Rewriting

Uses Software

• Haskell

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Termination of term rewriting using dependency pairs
• Normalization of Infinite Terms
• Automated Termination Analysis for Haskell: From Term Rewriting to Programming Languages
• The $\Pi^0_2$ -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity)
• Degrees of Undecidability in Term Rewriting
• Logic for Programming, Artificial Intelligence, and Reasoning