Degrees of Undecidability in Term Rewriting

DOI10.1007/978-3-642-04027-6_20MaRDI QIDQ3644753zbMATH OpenOpenAlexFDO

Authors 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) Hierarchies of computability and definability (03D55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42)

Recommendations

• Levels of undecidability in rewriting
• Relative undecidability in term rewriting. I: The termination hierarchy
• Reachability and confluence are undecidable for flat term rewriting systems
• scientific article; zbMATH DE number 1086665
• Relative undecidability in term rewriting. II: The confluence hierarchy

Cites work

• Automated Termination Analysis for Haskell: From Term Rewriting to Programming Languages
• Degrees of Undecidability in Term Rewriting
• scientific article; zbMATH DE number 3577197 (Why is no real title available?)
• scientific article; zbMATH DE number 1543072 (Why is no real title available?)
• scientific article; zbMATH DE number 3248792 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Infinitary normalization
• Logic for Programming, Artificial Intelligence, and Reasoning
• Normalization of Infinite Terms
• Termination of term rewriting using dependency pairs
• The \Pi^0_2 -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity)

Cited in

(15)

• 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
• Highlights in infinitary rewriting and lambda calculus
• Regaining cut admissibility in deduction modulo using abstract completion
• The exact hardness of deciding derivational and runtime complexity
• Least upper bounds on the size of Church-Rosser diagrams in term rewriting and -calculus
• The \Pi^0_2 -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity)
• Degrees of Undecidability in Term Rewriting
• Decreasing diagrams for confluence and commutation
• New Undecidability Results for Properties of Term Rewrite Systems
• Complexity of Fractran and Productivity
• Behavioral rewrite systems and behavioral productivity
• Levels of undecidability in rewriting
• Undecidable properties of flat term rewrite systems

Describes a project that uses

Uses Software

• Haskell

This page was built for publication: Degrees of Undecidability in Term Rewriting

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