Extension functions for multiset orderings

DOI10.1016/0020-0190(87)90003-2MaRDI QIDQ1104349zbMATH OpenOpenAlexWikidataFDO

Authors Ursula Martin Webb

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90003-2

zbMATH Keywords

bagmultiset orderingordered multisetprogram terminationterm-rewriting systemstermination ordering

Mathematics Subject Classification ID

Ordered sets (06A99) Specification and verification (program logics, model checking, etc.) (68Q60)

Review text

A multiset or bag on a set S is an unordered sequence of elements of S. \textit{N. Dershowitz} and \textit{Z. Manna} showed [Commun. ACM 22, 465-476 (1979; Zbl 0431.68016)] how to construct an ordering \(\gg\) on \({\mathcal M}(S)\), the set of multisets in S, from any ordering \(>\) on the underlying set S. This order, which we shall call the standard multiset ordering, has proved particularly useful in proofs of program termination and in constructing orderings which prove the termination of term- rewriting systems. In this paper we shall construct many other orderings on multisets which reflect the ordering on S, and share the usual properties of multiset orderings.

Recommendations

• scientific article; zbMATH DE number 3986676
• A geometrical approach to multiset orderings
• Partial orderings for sets of multisets
• Extension orderings
• A Computation of the Maximal Order Type of the Term Ordering on Finite Multisets

Cites work

• On multiset orderings
• Proving termination with multiset orderings
• Termination of rewriting

Cited in

(11)

• Termination of rewriting
• A geometrical approach to multiset orderings
• Partial orderings for sets of multisets
• Bag equivalence via a proof-relevant membership relation
• scientific article; zbMATH DE number 3986676 (Why is no real title available?)
• The order types of termination orderings on monadic terms, strings and multisets
• scientific article; zbMATH DE number 2154398 (Why is no real title available?)
• On multiset ordering
• On the formalization of termination techniques based on multiset orderings
• An alternative proof of the well-foundedness of the nested multiset ordering
• Leanest quasi-orderings

This page was built for publication: Extension functions for multiset orderings

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