Simple termination is difficult

DOI10.1007/BF01225647zbMath0815.68064MaRDI QIDQ1343111

Aart Middeldorp, Bernhard Gramlich

Publication date: 31 January 1995

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

zbMATH Keywords

undecidabilitysimplification ordersterminating term rewriting system

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items

On termination of one rule rewrite systems ⋮ Problems in rewriting III ⋮ On the modularity of termination of term rewriting systems ⋮ Proving termination of context-sensitive rewriting by transformation ⋮ Simple termination of rewrite systems ⋮ Levels of undecidability in rewriting ⋮ Order-sorted Homeomorphic Embedding Modulo Combinations of Associativity and/or Commutativity Axioms* ⋮ Invariants, patterns and weights for ordering terms ⋮ NEW RESULTS ON COMPUTABILITY OF RECURRENCE EQUATIONS ⋮ Relative undecidability in term rewriting. I: The termination hierarchy ⋮ Relative undecidability in term rewriting. II: The confluence hierarchy ⋮ Computability of affine non-conditional recurrent systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The undecidability of self-embedding for term rewriting systems
• Termination of rewriting
• Modularity of simple termination of term rewriting systems with shared constructors
• Simulation of Turing machines by a regular rewrite rule
• Generalized sufficient conditions for modular termination of rewriting
• The undecidability of the Turing machine immortality problem