Proving termination for term rewriting systems
A common method for proving termination of a term rewriting system is to show that the rewrite relation is included in a well-founded relation on the considered set of terms, called termination orderings. Section 2 gives an order-theoretic analysis of the multiset ordering, the recursive path ordering, and the lexicographic path ordering. These precedence- based termination orderings are studied with respect to order types and maximal order types. For obtaining strong generalizations of precedence- based termination orderings, (in Section 3) to any (existing) ordinal notation system \(T\) and any partial ordering \(P\) is associated a (not necessarily well-founded) notation system \(T_ P\), which is constructed out of elements of the domain of \(P\) in the same way \(T\) is constructed out of its single ``base element. For certain particular notation systems \(T\) it is shown that essential order-theoretic properties of the partial ordering (e.g. linearity, well-foundedness, and well-partial orderedness) are transmitted to the notation system \(T_ P\). The author conjectures that these facts are special cases of a general transfer principle relating notation systems \(T_ P\) to partial orderings \(P\). For the entire collection see [Zbl 0772.68004].
- Termination of rewriting
- Using unavoidable set of trees to generalize Kruskal's theorem
- Proving termination of (conditional) rewrite systems. A semantic approach
- Termination of term rewriting: Interpretation and type elimination
- Equational derivation vs. computation
- A proof of strongly uniform termination for Gödel's \(T\) by methods from local predicativity
- Proof-theoretic analysis of termination proofs
- Well-partial-orderings and the big Veblen number
- Certifying term rewriting proofs in ELAN
- Termination proof of term rewriting system with the multiset path ordering. A complete development in the system Coq
- Program size complexity of correction grammars in the Ershov hierarchy
- Termination Proof of S-Expression Rewriting Systems with Recursive Path Relations
- Proving Termination Using Recursive Path Orders and SAT Solving
- A Computation of the Maximal Order Type of the Term Ordering on Finite Multisets
- scientific article; zbMATH DE number 3905845 (Why is no real title available?)
- scientific article; zbMATH DE number 3930339 (Why is no real title available?)
- scientific article; zbMATH DE number 4007716 (Why is no real title available?)
- On a duality between Kruskal and Dershowitz theorems
- scientific article; zbMATH DE number 1179979 (Why is no real title available?)
- Syntactical analysis of total termination
- Termination of theorem proving by reuse
- scientific article; zbMATH DE number 794239 (Why is no real title available?)
- scientific article; zbMATH DE number 862680 (Why is no real title available?)
- Gap embedding for well-quasi-orderings
- A local termination property for term rewriting systems
- Time bounded rewrite systems and termination proofs by generalized embedding
- Topics in termination
- Total termination of term rewriting
- On the formalization of termination techniques based on multiset orderings
- An order-theoretic characterization of the Howard-Bachmann-hierarchy
- Proof Terms for Infinitary Rewriting
- An alternative proof of the well-foundedness of the nested multiset ordering
- A proof-theoretic study of abstract termination principles
- A general theorem on termination of rewriting
- Termination of Fair Computations in Term Rewriting
- Proving positive almost-sure termination
- Combining termination proofs in model transformation systems
- An ordinal calculus for proving termination in term rewriting
- A survey of ordinal interpretations of type ɛ0 for termination of rewriting systems
- The hierarchy of terminating recursive programs over N
- Well partial orders
- Maximum linearizations of lower sets in \(\mathbb{N}^m\) with application to monomial ideals
- Proving termination of context-sensitive rewriting by transformation
- On the recursive decomposition ordering with lexicographical status and other related orderings
- Termination of just/fair computations in term rewriting
This page was built for publication: Proving termination for term rewriting systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4202962)