Relative undecidability in term rewriting. II: The confluence hierarchy

DOI10.1006/inco.2002.3120zbMath1012.68097OpenAlexW2312503573MaRDI QIDQ1854560

Aart Middeldorp, Enno Ohlebusch, Alfons Geser, 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 (6)

A Confluent Rewriting System Having No Computable, One-Step, Normalizing Strategy ⋮ Levels of undecidability in rewriting ⋮ Certification of Classical Confluence Results for Left-Linear Term Rewrite Systems ⋮ Relative undecidability in term rewriting. I: The termination hierarchy ⋮ Relative undecidability in term rewriting. II: The confluence hierarchy ⋮ Undecidable Properties on Length-Two String Rewriting Systems

Cites Work

• 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
• Decision problems for semi-Thue systems with a few rules
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Relative undecidability in term rewriting. II: The confluence hierarchy