Proving termination for term rewriting systems

From MaRDI portal





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].




Cited in
(45)








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)