Simple termination is difficult
From MaRDI portal
Publication:1343111
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)
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