scientific article; zbMATH DE number 3930339
[For the entire collection see Zbl 0568.00022.] The paper presents a survey of methods for proving termination of term rewriting systems. First, undecidability of termination of rewriting systems is proved. Then, various criteria for checking sufficient conditions for termination are presented. The exposition begins with the use of well-founded orderings and simplification orderings for termination proofs, and continues through an exposition of quasi- orderings and multiset orderings to path orderings based on an underlying operator precedence (a partial ordering of the operators). Eventually, results concerning restricted classes of rewriting systems are presented: termination of combinations of rewriting systems and termination criteria for special classes of rewriting systems. Variants of the orderings suitable form the implementational point of view are also discussed. A lot of examples is provided throughout the paper, illustrating the orderings introduced and comparing their usage in termination proofs of various rewriting systems.
- Termination orderings for associative-commutative rewriting systems
- Termination of rewriting
- Simplifying conditional term rewriting systems: Unification, termination and confluence
- Counterexamples to termination for the direct sum of term rewriting systems
- A geometrical approach to multiset orderings
- Schematization of infinite sets of rewrite rules generated by divergent completion processes
- Complexity analysis of term-rewriting systems
- Simplification orderings: Putting them to the test
- Proving termination of (conditional) rewrite systems. A semantic approach
- Termination of term rewriting: Interpretation and type elimination
- On the modularity of termination of term rewriting systems
- Simple termination of rewrite systems
- Pattern-matching algorithms based on term rewrite systems
- Proof of termination of the rewriting system SUBSET on CCL
- A strong restriction of the inductive completion procedure
- Automatic proofs by induction in theories without constructors
- Outside opportunities and termination
- Termination and normalisation under strategy proofs in ELAN
- Local termination: theory and practice
- Termination of rewriting under strategies
- Cancellation
- Order-sorted termination: the unsorted way
- Proving termination properties with \textsc{mu-term}
- scientific article; zbMATH DE number 3870584 (Why is no real title available?)
- scientific article; zbMATH DE number 3870640 (Why is no real title available?)
- Termination Proof of S-Expression Rewriting Systems with Recursive Path Relations
- Detecting Non-termination of Term Rewriting Systems Using an Unfolding Operator
- Orderings and Constraints: Theory and Practice of Proving Termination
- TERMINATION OF ABSTRACT REDUCTION SYSTEMS
- Local Termination
- scientific article; zbMATH DE number 3905845 (Why is no real title available?)
- scientific article; zbMATH DE number 4007716 (Why is no real title available?)
- scientific article; zbMATH DE number 4047065 (Why is no real title available?)
- scientific article; zbMATH DE number 4090779 (Why is no real title available?)
- scientific article; zbMATH DE number 408817 (Why is no real title available?)
- scientific article; zbMATH DE number 1179979 (Why is no real title available?)
- scientific article; zbMATH DE number 1748590 (Why is no real title available?)
- Syntactical analysis of total termination
- Extension orderings
- scientific article; zbMATH DE number 794239 (Why is no real title available?)
- scientific article; zbMATH DE number 862680 (Why is no real title available?)
- A local termination property for term rewriting systems
- Priority rewriting: Semantics, confluence, and conditionals
- Negation with logical variables in conditional rewriting
- Extensions and comparison of simplification orderings
- Time bounded rewrite systems and termination proofs by generalized embedding
- Program transformation and rewriting
- Topics in termination
- It is undecidable whether the Knuth-Bendix completion procedure generates a crossed pair
- First-order formative rules
- Nagoya termination tool
- Simple termination revisited
- Termination of processes
- Orderings for innermost termination
- Leanest quasi-orderings. Preliminary version.
- Termination of term rewriting by interpretation
- A survey of ordinal interpretations of type ɛ0 for termination of rewriting systems
- On sufficient completeness of conditional specifications
- An universal termination condition for solving goals in equational languages
- Processes, Terms and Cycles: Steps on the Road to Infinity
- The termination hierarchy for term rewriting
- Dismissal power
- Natural termination
- Termination by completion
- On word problems in Horn theories
- Termination orders for 3-polygraphs
- Summarization for termination: No return!
- Leanest quasi-orderings
- Weighted graphs: A tool for studying the halting problem and time complexity in term rewriting systems and logic programming
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3703288)