Relative undecidability in term rewriting. I: The termination hierarchy

DOI10.1006/inco.2002.3120zbMath1012.68096OpenAlexW2312503573MaRDI QIDQ1854559

Aart Middeldorp, Alfons Geser, Enno Ohlebusch, Hans Zantema

Publication date: 14 January 2003

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

Full work available at URL: https://doi.org/10.1006/inco.2002.3120

Mathematics Subject Classification ID

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

Related Items

Levels of undecidability in rewriting ⋮ Decision problems for semi-Thue systems with a few rules ⋮ Context-sensitive rewriting strategies ⋮ Undecidable Properties on Length-Two String Rewriting Systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The undecidability of self-embedding for term rewriting systems
• Simulation of Turing machines by a regular rewrite rule
• Termination of term rewriting: Interpretation and type elimination
• On termination of one rule rewrite systems
• Simple termination is difficult
• Omega-termination is undecidable for totally terminating term rewriting systems
• Simple termination of rewrite systems
• Relative undecidability in term rewriting. II: The confluence hierarchy
• Total termination of term rewriting is undecidable
• Total termination of term rewriting
• The order types of termination orderings on monadic terms, strings and multisets
• Term Rewriting and All That
• Non-Looping String Rewriting
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• A variant of a recursively unsolvable problem

This page was built for publication: Relative undecidability in term rewriting. I: The termination hierarchy