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
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
How to Cite
Issue
Section
License
Copyright (c) 2024 UMYU Scientifica
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
&
