Relative undecidability in term rewriting. I: The termination hierarchy

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

Enno Ohlebusch, Aart Middeldorp, Hans Zantema, Alfons Geser

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

03D35: Undecidability and degrees of sets of sentences

68Q42: Grammars and rewriting systems

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