Exploring Partially Ordered Multisets: Definitions, Applications, and Combinatorial Parameters
DOI:
https://doi.org/10.56919/usci.2433.009Keywords:
Multiset, partial order, ordered multiset, combinatorial parametersAbstract
A partially ordered set 
is a nonempty set 
equipped with a partial order 
. Ordered structures are useful for representing application problems that involve comparable and incomparable parameters or inputs. Ordered sets are studied based on classical set theory, where objects in a collection are assumed to be distinct. However, mathematical objects are not always distinguishable, especially in applications. Multisets are mathematical models of entities with repetition. Multiset theory is distinguished from a set by carrying information on the number of times an element appears in a given collection, making it suitable for modeling real-life situations. A multiset 
over can be formally defined as a cardinal-valued function, 
such that 
implies 
is a cardinal number and 
, where
denotes the number of times 
occurs in . Multisets generalize the classical sets and are apt for representing partial orders. There has been a growing interest in extending results on ordered sets to multisets. Unlike in classical set theory, there is still no unanimous way of studying foundational concepts in multisets. For instance, different approaches have been proposed for studying orderings on multisets due to the multiplicity parameter that is peculiar to multisets. This paper surveys studies on ordered multisets and compares existing orderings proposed on multiset structures. In particular, cases where the definition results in a partial order are of great interest in this exposition; their properties and theoretical implications make them suitable for application. We focus on definitions consistent with the Dershowitz-Manna multiset ordering, usually referred to as the standard multiset ordering, due to their relevance in applications, e.g., in computer programming. The strengths and possible limitations of the multiset orderings presented in this work are highlighted. This would aid in identifying potentially suitable definitions when dealing with studies that involve ordered multisets. Combinatorial parameters that have been studied on ordered multiset structures are also presented in this paper. The generalized notions of these parameters are investigated with some recommendations.
References
Alhazor, A., Freund, R., Ivanor, S. et al. (2024). P systems with reactive membranes. Journal of Membrane Computing, 6: 82-93. DOI: https://doi.org/10.1007/s41965-024-00144-1
Anusuya Ilamathi, V. S., & Vimala, J. (2018). Multi-criteria decision making on lattice ordered multisets. In: Thampi, S., Mitra, S., Mukhopadhyay, J., Li,KC., James, A., Berreti, S. (eds) Intelligent Systems Technologies and Applications. ISTA 2017. Advances in Intelligent Systems and Computing, vol 683. Springer, Cham. DOI: https://doi.org/10.1007/978-3-319-68385-0_34
Balogun, F., & Singh, D. (2017). Some characterizations for the dimension of ordered multisets. FUDMA Journal of Sciences, 1(2), 84-87.
Balogun, F., Singh, D., & Aliyu, S. (2022). Multisets linear extensions with a heuristic algorithm, Annals of Fuzzy Mathematics and Informatics, 24(2), 129-136.
Balogun, F., Singh, D., & Tella, Y. (2020). Realizers of partially ordered multisets, Theory and Applications of Mathematics and Computer Science, 10(2), 1-6.
Balogun, F., Singh, D., & Tella, Y. (2021). Maximal and maximum antichains of ordered multisets, Annals of Fuzzy Mathematics and Informatics, 21(1), 105-112.
Balogun, F., & Tella, T. (2018). A study on some substructures of ordered multisets, FUDMA Journal of Sciences, 2 (1), 201-205.
Beaten, J. C. M., & Weijland, W. P. (1990). Process Algebra. Cambridge University Press, Cambridge. DOI: https://doi.org/10.1017/CBO9780511624193
Blanchet-Sadri, F. (2012). Algorithmic combinatorics of partial words. International Journal of Foundations of Computer Science, 1189-1206. DOI: https://doi.org/10.1142/S0129054112400473
Blizard, W. (1988). Multiset theory. Notre Dame Journal of Formal Logic, 30(1), 36-66. DOI: https://doi.org/10.1305/ndjfl/1093634995
Blizard, W. (1991). The development of multiset theory. Mod. Log, 1(4), 319-352.
Caspard, N., Leclerc, B., & Monjardet, B. (2012). Chains and antichains. In: Finite Ordered Sets: Concepts, Results and Uses. Encyclopedia of Mathematics and its Applications. Cambridge University Press: 107-129. DOI: https://doi.org/10.1017/CBO9781139005135.005
Chen, S., Liu, J., Wang, H., & Augusto, J. C. (2013). Ordering based decision making – A survey. Information Fusion, 14(4): 521-531. DOI: https://doi.org/10.1016/j.inffus.2012.10.005
Conder, M., Marshall, S., & Slinko, A. (2007). Orders on Multisets and Discrete Cones. Order, 24, 277-296. DOI: https://doi.org/10.1007/s11083-007-9073-1
Dang, H. (2014). A single-sorted theory of multisets. Notre Dame Journal of Formal Logic, 55(3) (2014), 299-332. DOI: https://doi.org/10.1215/00294527-2688042
Dershowitz, N., & Ellerman, E. C. (2007). Leanest quasi-orderings. Information and Computation, 205(4): 535-556. DOI: https://doi.org/10.1016/j.ic.2006.10.007
Dershowitz, N., & Manna, Z. (1979). Proving termination with multiset orderings. Communications of the Journal of Association for Computing Machinery, 22(8), 465-476. DOI: https://doi.org/10.1145/359138.359142
Fattore, M. (2014). Partially ordered sets. In: Michalos, A. C. (eds) Encyclopedia of Quality of Life and Well-being Research. Springer. Dordrecht. DOI: https://doi.org/10.1007/978-94-007-0753-5_2082
Felisiak, P. A., Qin, K., & Li, G. (2020). Generalized multiset theory. Fuzzy Sets and Systems, 380, 104-130. DOI: https://doi.org/10.1016/j.fss.2019.05.015
Garmendia, L., Gonzalez del Cumpo & Recusens, J. (2017). Partial orderings for hesitant fuzzy sets. International Journal of Approximate Reasoning, 84: 159-167. DOI: https://doi.org/10.1016/j.ijar.2017.02.008
Girish, K. P., & Sunil, J.J. (2009). General relations between partially ordered multisets and their chains and antichains. Mathematical Communications, 14(2), 193-205.
Gischer, J. (1984). Partial orders and the axiomatic theory of shuffle. PhD Thesis, Computer Science Department, Stanford University.
Gischer, J. (1988). The equational theory of pomsets. Theoretical Computer Science, 61, 199-224. DOI: https://doi.org/10.1016/0304-3975(88)90124-7
Gisin, V., & Volkova, E. S. (2024). Equivalence relations on Multisets. 2024 XXVII International Conference on Soft Computing and Measurements (SCM). Saint Petersburg, Russian Federation. DOI: https://doi.org/10.1109/SCM62608.2024.10554263
Gosh, A. (2019). A study of some combinatorial sets in partial semigroups. Asian-European Journal of Mathematics.
Grabowski, J. (1981). On partial languages. Fundamenta Informaticae, 4, 427-498. DOI: https://doi.org/10.3233/FI-1981-4210
Huet, G., & Oppen, D. C. (1980). Equations and rewrite rules: a survey, in R. Book, ed., Formal Languages Perspectives and Open Problems, Academy Press, New York. DOI: https://doi.org/10.1016/B978-0-12-115350-2.50017-8
Jokela, J. (2023). General mixed lattices. Order. DOI: https://doi.org/10.1007/s11083-023-09648-4
Joret, G., Micek, P., Milans, K., Trotter, W. T., Walczak, B., & Wang, R. (2016). Tree-width and dimension. Combinatorica, 36, 431-450. DOI: https://doi.org/10.1007/s00493-014-3081-8
Jouannaud, J-P., & Lescanne, P. (1982). On multiset orderings. Information Processing Letters, 15(2), 57-63. DOI: https://doi.org/10.1016/0020-0190(82)90107-7
Jurgense, H. (2020). Multisets, heaps, bags, families: What is a multiset? Mathematical Structures in Computer Science, 30: 139-158. DOI: https://doi.org/10.1017/S0960129519000215
Knuth, D. E. (1981). The Art of Computer Programming (Seminumerical Algorithms), volume 2. Addison-Wesley, Reading, Massachusetts, second edition.
Krom, M. (1985). Partial ordering for sets of multisets. Algebra Universalis, 21, 156-162. DOI: https://doi.org/10.1007/BF01188051
Kuba, M. (2022). On multisets, interpolated multiple zeta values and limit laws. The Electronic Journal of Combinatorics, 29(1): #P1.48. DOI: https://doi.org/10.37236/10305
Liu, Y., Nicolescu, R., & Sun, J. (2021). An efficient labeled nested multiset unification algorithm. Journal of Membrane Computing 3, 194-204. DOI: https://doi.org/10.1007/s41965-021-00076-0
Martin, U. (1989). A geometrical approach to multiset orderings. Theoretical Computer Science, 67, 37-54. DOI: https://doi.org/10.1016/0304-3975(89)90020-0
Mazurkiewicz, A. (1984). Traces, Histories, Graphs: Instances of a process monoid. Proceedings of the Conference on Mathematical Foundations of Computer Science, Springer-Verlag LNCS, 176. DOI: https://doi.org/10.1007/BFb0030293
Muren, Liu, C., & Cui, W. (2023). The relationships among group decision-making units based on partial ordered set. Computers and Industrial Engineering, 179. DOI: https://doi.org/10.1016/j.cie.2023.109173
Muren, Liu, C., & Cui, W. et al., (2022). Special relationship among decision-making units based on partially ordered set and new evaluation and projection methods. Journal of Systems Science and Systems Engineering, 31(1): 226-246. DOI: https://doi.org/10.1007/s11518-022-5519-7
Paun, G. (2010). A quick guide to membrane computing. The Journal of Logic and Algebraic Programming, 79: 291-294. DOI: https://doi.org/10.1016/j.jlap.2010.04.002
Pratt, V. R. (1986). Modelling concurrency with partial orders. International Journal of Parallel Programming, 15, 33-71. DOI: https://doi.org/10.1007/BF01379149
Qiao, J., & Hu, B. Q. (2020). On decision evaluation functions in generalized three-way decision spaces. Information Sciences, 507: 733-754. DOI: https://doi.org/10.1016/j.ins.2018.07.032
Rensink, A. (1996). Denotational, causal, and operational determinism in event structures, in Trees in Algebra and Programming- CAAP ’96, edited by H. Kirchner. 1059 Lecture Notes in Computer Science, Springer-Verlag, Berlin. DOI: https://doi.org/10.1007/3-540-61064-2_43
Savaglio, E., & Vannucci, S. (2007). On multidimensional inequality in partitions of multisets. Quaderno de Dipartimento di Economica Politica N504. University of Siena.
Singh, D., Ibrahim, A.M., Yohanna, T., & Singh, J.N. (2007). An overview of the applications of multisets. Novi Sad Journal of Mathematics, 37(2): 73-92.
Singh, D., Tella, Y., & Singh, J. N. (2012). Topological sorts of a multiset ordering. IJCSST, 5(2): 101-105.
Wilson, A. T. (2016). An extension of MacMahon’s equidistribution theorem to ordered multiset partitions. The Electronic Journal of Combinatorics, 23(1) #P1.5 DOI: https://doi.org/10.37236/5485
Yap, K. T., Wehlan, D., & Zaguia , I. (2021). Permutations Avoiding Certain Partially-Ordered Patterns. The Electronic Journal of Combinatorics. DOI: https://doi.org/10.37236/10206
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
UMYU Scientifica recognizes the importance of protecting authors’ intellectual property while promoting the free exchange of scientific knowledge. The journal adopts a copyright-retention model that empowers authors to maintain ownership of their work while granting the journal rights necessary for publication and dissemination.
1. Copyright Ownership
Authors publishing with UMYU Scientifica retain full copyright and publishing rights to their work. By submitting a manuscript, authors agree to grant the journal a non-exclusive license to publish, reproduce, distribute, and archive the article in all forms and media for the purpose of scholarly communication.
2. Licensing Terms
All articles are published under the Creative Commons Attribution–NonCommercial (CC BY-NC) license.
This license permits others to:
- Share - copy and redistribute the material in any medium or format.
- Adapt - remix, transform, and build upon the material.
- For non-commercial purposes only, provided that proper credit is given to the original author(s) and UMYU Scientifica as the source, a link to the license is provided, and any modifications are clearly indicated.
Commercial reuse or distribution of the content requires written permission from both the author and the editorial office.
3. Author Rights
Authors are free to:
- Deposit all versions of their manuscript (preprint, accepted version, and published version) in institutional, disciplinary, or public repositories without embargo.
- Use and distribute their published article for non-commercial scholarly purposes, including teaching, conference presentations, and research sharing.
- Include their work in future books, theses, or compilations, provided proper citation to the journal is made.
4. Publisher’s Rights
Upon publication, UMYU Scientifica retains the right to:
- Host, index, and disseminate the article through the journal’s website and partner databases.
- Archive the content in long-term preservation systems such as the PKP Preservation Network (PKP-PN) and the Umaru Musa Yar’adua University Institutional Repository.
5. Attribution and Citation
Users must give appropriate credit to the author(s), include a link to the article’s DOI or the journal webpage, and indicate if changes were made. Proper citation is required whenever the work is reused or referenced.
6. License Reference
For detailed terms of use, please refer to the Creative Commons Attribution–NonCommercial 4.0 International License (CC BY-NC 4.0):
https://creativecommons.org/licenses/by-nc/4.0/
