Simple termination is difficult

DOI10.1007/BF01225647MaRDI QIDQ1343111zbMATH OpenFDO

Authors Aart Middeldorp, Bernhard Gramlich

Publication date 31 January 1995

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

Full work available at URL https://doi.org/10.1007/BF01225647

zbMATH Keywords

simplification ordersterminating term rewriting systemundecidability

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Simple termination is difficult
• scientific article; zbMATH DE number 759443
• Simple termination revisited
• Simple termination of rewrite systems
• scientific article; zbMATH DE number 4060699

Cites work

• Generalized sufficient conditions for modular termination of rewriting
• scientific article; zbMATH DE number 1638661 (Why is no real title available?)
• scientific article; zbMATH DE number 3860380 (Why is no real title available?)
• scientific article; zbMATH DE number 4035120 (Why is no real title available?)
• scientific article; zbMATH DE number 49211 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• Modularity of simple termination of term rewriting systems with shared constructors
• Simulation of Turing machines by a regular rewrite rule
• Termination of rewriting
• The undecidability of self-embedding for term rewriting systems
• The undecidability of the Turing machine immortality problem

Cited in

(26)

• The undecidability of self-embedding for term rewriting systems
• Termination of rewriting
• Simulation of Turing machines by a regular rewrite rule
• On termination of one rule rewrite systems
• On the modularity of termination of term rewriting systems
• Omega-termination is undecidable for totally terminating term rewriting systems
• Simple termination of rewrite systems
• Invariants, patterns and weights for ordering terms
• Computability of affine non-conditional recurrent systems
• Relative undecidability in term rewriting. I: The termination hierarchy
• Relative undecidability in term rewriting. II: The confluence hierarchy
• Decidability of innermost termination and context-sensitive termination for semi-constructor term rewriting systems
• scientific article; zbMATH DE number 4035120 (Why is no real title available?)
• scientific article; zbMATH DE number 4060699 (Why is no real title available?)
• scientific article; zbMATH DE number 1183250 (Why is no real title available?)
• scientific article; zbMATH DE number 759443 (Why is no real title available?)
• Simulation of Turing machines by a left-linear rewrite rule
• Simple termination is difficult
• Problems in rewriting III
• Equilibrium and termination
• Simple termination revisited
• New results on computability of recurrence equations
• Levels of undecidability in rewriting
• Linear termination is undecidable
• Summarization for termination: No return!
• Proving termination of context-sensitive rewriting by transformation

This page was built for publication: Simple termination is difficult

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1343111)