Termination proofs by multiset path orderings imply primitive recursive derivation lengths

DOI10.1016/0304-3975(92)90289-RzbMath0759.68045OpenAlexW1489374747MaRDI QIDQ1200982

Dieter Hofbauer

Publication date: 16 January 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90289-r

zbMATH Keywords

terminationterm rewriting systemmultiset path orderings

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items

Reduction relations for monoid semirings, Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones, On the Computational Content of Termination Proofs, Total termination of term rewriting, Simple termination of rewrite systems, A characterisation of multiply recursive functions with Higman's lemma., Analysing the implicit complexity of programs., An upper bound on the derivational complexity of Knuth-Bendix orderings., Proving Quadratic Derivational Complexities Using Context Dependent Interpretations, The derivational complexity of string rewriting systems, Automated Complexity Analysis Based on the Dependency Pair Method, Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths, Quasi-interpretations. A way to control resources, Some new results on decidability for elementary algebra and geometry, Derivation lengths and order types of Knuth--Bendix orders, The Hydra battle and Cichon's principle, Complexity Analysis by Rewriting, A lexicographic path order with slow growing derivation bounds, Total termination of term rewriting, Applications and extensions of context-sensitive rewriting, The Derivational Complexity Induced by the Dependency Pair Method, Derivational complexity and context-sensitive Rewriting, Invariants, patterns and weights for ordering terms

Cites Work

• Orderings for term-rewriting systems
• Termination of rewriting
• Path of subterms ordering and recursive decomposition ordering revisited
• Computability, complexity, logic. Transl. from the German
• Termination proofs and the length of derivations
• Extensions and comparison of simplification orderings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item