Current State of the Multisets Theory from the Essential Viewpoint
- PDF / 102,013 Bytes
- 7 Pages / 594 x 792 pts Page_size
- 23 Downloads / 241 Views
CURRENT STATE OF THE MULTISETS THEORY FROM THE ESSENTIAL VIEWPOINT V. N. Red’ko,a D. B. Bui,a† and Y. A. Grishkoa‡
UDC 004.422.6:510.21
Abstract. This paper reviews the state of the art in the theory of multisets, i.e., mathematical models of sets with repetitions (duplicates or copies of their elements). The corresponding bibliography is categorized as follows: the general theory of multisets, reviews, and application of multisets, in particular, in computer science. Keywords: set with repetitions, multiset. INTRODUCTION The proposed review is devoted to multisets, i.e., models of entities such as sets with repetitions (instances or duplicates of elements of such sets). Without going into discussing extensional and intensional aspects of these entities, we mention only the most important ones, namely, their plurality and exemplarness. The statement of the question about the relationship between the concepts of a set and a multiset at one level of abstraction (as D. Knuth tries to do) is at least fundamentally incorrect since the mentioned concepts are, in essence, at different abstraction levels. Here, they should be simultaneously considered at two abstraction levels (polyabstractness rather than monoabstractness at the subject level), the introduction and elimination of abstraction should be considered, etc. All these deep essential questions go beyond the scope of this article whose objective is much more local and consists of showing the actual state of the art in the multisets theory and its applications. In other words, for the mentioned object domain, we will consider only factography rather than factology. The authors consciously abstract themselves from an interpretation of the concrete results being discussed as applied to multisets. We briefly dwell on the essential approach. Generally speaking, this approach presumes the consideration of not only extensional aspects (i.e., the aspects singling out the entity being considered from a universe of entities as an abstraction of the closedness in the actuality of a universe of objects) but also intensional aspects (i.e., aspects of the internal structure of the entity being considered; for more details, see [1] and its bibliography). A comprehensive discussion of each of these aspects and especially their interaction (interface) goes far beyond the framework of this article. Therefore, we only note that, for multisets, extensionality is conditioned by multiplicity and intensionality is conditioned by exemplarness. Informally speaking, multisets are sets with repetitions. The concept of a multiset (this especially pertains to the term itself) has appeared relatively recently though multisets are rather frequently used in practical problems. We note the following characteristic trait: in the classical field such as combinatorial analysis, multisets have appeared under the name of combinations with repetitions (see, for example, [2–5]; the term “multiset” itself arises in [5] and is formally defined as a function mapping the Cantor set into the set of natural
Data Loading...
