Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-02T16:56:43.638Z Has data issue: false hasContentIssue false

A note on the concept of multiset

Published online by Cambridge University Press:  17 April 2009

J.L. Hickman
Affiliation:
Department of Mathematics, Institute of Advanced Studies, Australian National University, PO Box 4, Canberra, ACT 2600, Australia.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In various papers on some of the theoretical aspects of computing, the reader is confronted with a mathematical entity called a “multiset”, and is told that a multiset is “an unordered collection of elements that may have repeated occurrences of identical elements” (see, for example, Nachum Dershowitz and Zohar Manna, “Proving termination with multiset orderings”, Lecture Notes in Computer Science, 71). These entities are then manipulated in accordance with the classical laws of set algebra. The purpose of this note is to present a formal foundation for this concept of multiset, and to show by means of examples that if this foundation is adopted then, although certain sections of classical set algebra can be applied to multisets, it certainly cannot be applied in total.

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1980

References

[1]Dershowitz, Nachum and Manna, Zohar, “Proving termination with multiset orderings”, Automata, Languages and Programming, 188202 (Proc. Sixth Colloquium, Graz, Austria, 1979. Lecture Notes in Computer Science 71. Springer-Verlag, Berlin, Heidelberg, New York, 1979).CrossRefGoogle Scholar
[2]Knuth, Donald E., Seminumerical algorithms: the art of computer programming, Volume 2 (Addison Wesley, Reading, Massachusetts; Menlo Park, California; London; 1969).Google Scholar