Exploring Partially Ordered Multisets: Definitions, Applications, and Combinatorial Parameters

Authors

DOI:

https://doi.org/10.56919/usci.2433.009

Keywords:

Multiset, partial order, ordered multiset, combinatorial parameters

Abstract

Study’s Excerpt/Novelty

  • This paper surveyed comparatively analysed existing orderings on multiset structures, with a particular focus on definitions that result in partial orders, such as those consistent with the Dershowitz-Manna multiset ordering.
  • By highlighting the strengths and limitations of these orderings, the study offers critical insights into their applicability in real-world scenarios, including computer programming.
  • Additionally, the paper explores generalized combinatorial parameters on ordered multiset structures, providing recommendations for their use in further studies.

Full Abstract

A partially ordered set (S,≼) is a nonempty set S 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 M over S can be formally defined as a cardinal-valued function, M:S→N such that x∈Dom (M) implies M(x) is a cardinal number and M(x)=m_M (x)>0, where m_M (x) denotes the number of times x occurs in M. 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 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. 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. 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. https://doi.org/10.1017/CBO9780511624193

Blanchet-Sadri, F. (2012). Algorithmic combinatorics of partial words. International Journal of Foundations of Computer Science, 1189-1206. https://doi.org/10.1142/S0129054112400473

Blizard, W. (1988). Multiset theory. Notre Dame Journal of Formal Logic, 30(1), 36-66. 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. 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. 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. 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. https://doi.org/10.1215/00294527-2688042

Dershowitz, N., & Ellerman, E. C. (2007). Leanest quasi-orderings. Information and Computation, 205(4): 535-556. https://doi.org/10.1145/359138.359142

Dershowitz, N., & Manna, Z. (1979). Proving termination with multiset orderings. Communications of the Journal of Association for Computing Machinery, 22(8), 465-476. https://doi.org/10.1016/j.ic.2006.10.007

Fattore, M. (2014). Partially ordered sets. In: Michalos, A. C. (eds) Encyclopedia of Quality of Life and Well-being Research. Springer. Dordrecht. 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. 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. 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. 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. 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. https://doi.org/10.37236/10305

Grabowski, J. (1981). On partial languages. Fundamenta Informaticae, 4, 427-498. 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. https://doi.org/10.1016/B978-0-12-115350-2.50017-8

Jokela, J. (2023). General mixed lattices. Order. https://doi.org/10.1007.s111083-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. 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. 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. 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. 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. 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. https://doi.org/10.1007/s41965-021-00076-0

Martin, U. (1989). A geometrical approach to multiset orderings. Theoretical Computer Science, 67, 37-54. 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. 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. 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. 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. https://doi.org/10.1007/978-3-642-11467-0

Pratt, V. R. (1986). Modelling concurrency with partial orders. International Journal of Parallel Programming, 15, 33-71. 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. 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. 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 https://doi.org/10.48550/arXiv.1508.06261

Yap, K. T., Wehlan, D., & Zaguia , I. (2021). Permutations Avoiding Certain Partially-Ordered Patterns. The Electronic Journal of Combinatorics. https://doi.org/10.37236/10206

Downloads

Published

2024-07-16

How to Cite

Balogun, F., Balami, H. M., & Madugu, A. (2024). Exploring Partially Ordered Multisets: Definitions, Applications, and Combinatorial Parameters. UMYU Scientifica, 3(3), 74–81. https://doi.org/10.56919/usci.2433.009