Fuzzy multiset regular languages and their basic characterizations

Martinek, Pavel

dc.title	Fuzzy multiset regular languages and their basic characterizations	en
dc.contributor.author	Martinek, Pavel
dc.relation.ispartof	Fuzzy Sets and Systems
dc.identifier.issn	0165-0114 Scopus Sources, Sherpa/RoMEO, JCR
dc.identifier.issn	1872-6801 Scopus Sources, Sherpa/RoMEO, JCR
dc.date.issued	2026
utb.relation.volume	531
dc.type	article
dc.language.iso	en
dc.publisher	Elsevier B.V.
dc.identifier.doi	10.1016/j.fss.2026.109761
dc.relation.uri	https://www.sciencedirect.com/science/article/pii/S0165011426000011
dc.relation.uri	https://www.sciencedirect.com/science/article/pii/S0165011426000011/pdfft?md5=574259d94b328fea8f87d4bce73ff4c7&pid=1-s2.0-S0165011426000011-main.pdf
dc.subject	fuzzy multiset regular languages	en
dc.subject	fuzzy multiset regular grammars	en
dc.subject	fuzzy multiset finite automata	en
dc.subject	deterministic fuzzy multiset finite automata	en
dc.subject	fuzzy multiset regular expressions	en
dc.subject	fuzzy multiset regular operations	en
dc.subject	fuzzy semilinear sets	en
dc.description.abstract	The paper provides a survey of several ways how to describe fuzzy multiset regular languages, i.e., languages generated by fuzzy multiset regular grammars. These languages can also be characterized by means of fuzzy multiset finite automata (both in general and in reduced forms), fuzzy multiset regular expressions, and as fuzzy multiset languages which can be expressed in a semilinear form. Moreover, it is pointed out that a prevailing number of already published papers concerning fuzzy multiset finite automata is based on a wrong definition. It is also shown that the name ‘deterministic fuzzy multiset finite automaton’ is often used incorrectly for automata deserving adjective pseudodeterministic.	en
utb.faculty	Faculty of Applied Informatics
dc.identifier.uri	http://hdl.handle.net/10563/1012753
utb.identifier.obdid	43886287
utb.identifier.scopus	2-s2.0-105027542252
utb.identifier.wok	001671329000001
utb.identifier.coden	FSSYD
utb.source	j-scopus
dc.date.accessioned	2026-02-19T10:08:26Z
dc.date.available	2026-02-19T10:08:26Z
dc.description.sponsorship	This research was supported by the Internal research project of the Faculty of Applied Informatics, Tomas Bata University in Zlin No. RVO/FAI/2024/004.
dc.description.sponsorship	Internal research project of the Faculty of Applied Informatics, Tomas Bata University in Zlin [RVO/FAI/2024/004]
dc.rights	Attribution 4.0 International
dc.rights.uri	http://creativecommons.org/licenses/by/4.0/
dc.rights.access	openAccess
utb.ou	Department of Mathematics
utb.contributor.internalauthor	Martinek, Pavel
utb.fulltext.affiliation	Pavel Martinek https://orcid.org/0000-0002-6540-1118 Department of Mathematics, Tomas Bata University in Zlín, nám. T. G. Masaryka 5555, 760 01 Zlín, Czech Republic E-mail address: pmartinek@utb.cz
utb.fulltext.dates	Received 21 December 2024 Received in revised form 31 December 2025 Accepted 2 January 2026 Available online 7 January 2026
utb.fulltext.references	[1] S.P. Jena, S.K. Ghosh, B.K. Tripathi, On the theory of bags and lists, Inf. Sci. 132 (1–4) (2001) 241–254. https://doi.org/10.1016/S0020-0255(01)00066-4 [2] D. Rocacher, On fuzzy bags and their application to flexible querying, Fuzzy Sets Syst. 140 (2003) 93–110. https://doi.org/10.1016/S0165-0114(03)00029-0 [3] W.D. Blizard, The development of multiset theory, Mod. Log. 1 (4) (1991) 319–352. [4] S.K. Chang, Picture processing grammar and its applications, Inf. Sci. 3 (1971) 121–148. https://doi.org/10.1016/S0020-0255(71)80002-6 [5] R. Helm, K. Marriott, M. Oderski, Building visual language parsers, in: S.P. Robertson, G.M. Olson, J.S. Olson (Eds.), CHI ’91: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, Association for Computing Machinery, New York, 1991, pp. 105–112. https://doi.org/10.1145/108844.108860 [6] J.P. Banâtre, A. Coutant, D. Le Metayer, A parallel machine for multiset transformation and its programming style, Future Gener. Comput. Syst. 4 (2) (1988) 133–144. https://doi.org/10.1016/0167-739X(88)90012-X [7] G. Berry, G. Boudol, The chemical abstract machine, Theor. Comput. Sci. 96 (1992) 217–248. https://doi.org/10.1016/0304-3975(92)90185-I [8] G. Păun, G. Rozenberg, A. Salomaa, DNA Computing: New Computing Paradigms, Springer-Verlag, Berlin, 1998. [9] G. Păun, Computing with membranes, J. Comput. Syst. Sci. 61 (2000) 108–143. https://doi.org/10.1006/jcss.1999.1693 [10] M. Kudlek, C. Martín-Vide, G. Păun, Toward a formal macroset theory, in: C.S. Calude, G. Păun, G. Rozenberg, A. Salomaa (Eds.), Multiset Processing — Mathematical, Computer Science, and Molecular Computing Points of View, LNCS, 2235, Springer, Berlin, 2001, pp. 123–133. https://doi.org/10.1007/3-540-45523-X_7 [11] E. Csuhaj-Varjú, C. Martín-Vide, V. Mitrana, Multiset automata, in: C.S. Calude, G. Păun, G. Rozenberg, A. Salomaa (Eds.), Multiset Processing — Mathematical, Computer Science, and Molecular Computing Points of View, LNCS, 2235, Springer, Berlin, 2001, pp. 69–83. https://doi.org/10.1007/3-540-45523-X_4 [12] S. Crespi-Reghizzi, D. Mandrioli, Commutative grammars, Calcolo 13 (2) (1976) 173–189. https://doi.org/10.1007/BF02575679 [13] Z. Křivka, A. Meduna, Jumping grammars, Int. J. Found. Comput. Sci. 26 (2015) 709–732. https://doi.org/10.1142/S0129054115500409 [14] A. Meduna, P. Zemek, Jumping finite automata, Int. J. Found. Comput. Sci. 23 (2012) 1555–1578. https://doi.org/10.1142/S0129054112500244 [15] J. Wang, M. Yin, W. Gu, Fuzzy multiset finite automata and their languages, Soft. Comput. 17 (3) (2013) 381–390. https://doi.org/10.1007/s00500-012-0913-6 [16] P. Martinek, Fuzzy multiset finite automata: determinism, languages, and pumping lemma, in: Z. Tang, J. Du, S. Yin, L. He, R. Li (Eds.), 2015 12th International Conference on Fuzzy Systems and Knowledge Discovery, IEEE, 2015, pp. 60–64. https://doi.org/10.1109/FSKD.2015.7381915 [17] S.P. Tiwari, V. Gautam, M.K. Dubey, On fuzzy multiset automata, J. Appl. Math. Comput. 51 (2016) 643–657. https://doi.org/10.1007/s12190-015-0924-4 [18] Y. Wang, Y. Li, Minimization of lattice multiset finite automata, J. Intell. Fuzzy Syst. 35 (1) (2018) 627–637. https://doi.org/10.3233/JIFS-161382 [19] M. Shamsizadeh, M.M. Zahedi, On reduced fuzzy multiset finite automata, Soft Comput. 26 (2022) 13381–13390. https://doi.org/10.1007/s00500-022-07549-z [20] J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd ed., Pearson Addison Wesley, Upper Saddle River, 2003. [21] M. Sipser, Introduction to the Theory of Computation, 2nd ed., Thomson Course Technology, Boston, 2006. [22] M. Kudlek, P. Totzke, G. Zetsche, Multiset pushdown automata, Fund. Inf. 93 (2009) 221–233. https://doi.org/10.3233/FI-2009-0098 [23] M. Kudlek, P. Totzke, G. Zetsche, Properties of multiset language classes defined by multiset pushdown automata, Fund. Inf. 93 (2009) 235–244. https://doi.org/10.3233/FI-2009-0099 [24] W.D. Blizard, Multiset theory, Notre Dame J. Form. Log. 30 (1) (1989) 36–66. https://doi.org/10.1305/ndjfl/1093634995 [25] P. Martinek, An adaptation of CYK algorithm to multiset languages, in: T. Simos, Ch. Tsitouras (Eds.), International Conference on Numerical Analysis and Applied Mathematics 2018, ICNAAM 2018, AIP Conference Proceedings, Vol. 1978, 2019, Article no. 450040. https://doi.org/10.1063/1.5114507 [26] Y. Li, W. Pedrycz, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids, Fuzzy Sets Syst. 156 (2005) 68–92. https://doi.org/10.1016/j.fss.2005.04.004 [27] A. Stamenković, M. Ćirić, Construction of fuzzy automata from fuzzy regular expressions, Fuzzy Sets Syst. 199 (2012) 1–27. https://doi.org/10.1016/j.fss.2012.01.007 [28] P. Martinek, Some closure properties of fuzzy multiset regular languages, in: Proceedings of the 2018 Joint 10th International Conference on Soft Computing and Intelligent Systems and 19th International Symposium on Advanced Intelligent Systems, SCIS-ISIS 2018, IEEE, 2018, pp. 587–591. https://doi.org/10.1109/SCIS-ISIS.2018.00102 [29] J.R. González de Mendívil, J.R. Garitagoitia, Fuzzy languages with infinite range accepted by fuzzy automata: Pumping Lemma and determinization procedure, Fuzzy Sets Syst. 249 (2014) 1–26. https://doi.org/10.1016/j.fss.2014.02.006 [30] A. Salomaa, Formal Languages, Academic Press, New York, 1973. [31] J. DeBenedetto, D. Chiang, Algorithms and training for weighted multiset automata and regular expressions, in: C. Câmpeanu (Ed.), Implementation and Application of Automata, 23rd International Conference CIAA 2018, LNCS, 10977, Springer, Berlin, 2018, pp. 146–158. https://doi.org/10.1007/978-3-319-94812-6_13 [32] M. Droste, W. Kuich, H. Vogler (Eds.), Handbook of Weighted Automata, Springer, Berlin, 2009. [33] R. Barták, Automaty a gramatiky, Lekce 5 [Automata and Grammars, Lecture 5, PowerPoint Slides]. Charles University in Prague, 2024. (In Czech) https://ktiml.mff.cuni.cz/~bartak/automaty/lectures/lecture05.pdf [Accessed January 13, 2026]. [34] S. Ginsburg, The Mathematical Theory of Context-free Languages, McGraw-Hill, New York, 1966. [35] M. Kudlek, V. Mitrana, Normal forms of grammars, finite automata, abstract families, and closure properties of multiset languages, in: C.S. Calude, G. Păun, G. Rozenberg, A. Salomaa (Eds.), Multiset Processing — Mathematical, Computer Science, and Molecular Computing Points of View, LNCS, 2235, Springer, Berlin, 2001, pp. 135–146. https://doi.org/10.1007/3-540-45523-X_8 [36] R. Bělohlávek, Determinism and fuzzy automata, Inf. Sci. 143 (2002) 205–209. https://doi.org/10.1016/S0020-0255(02)00192-5 [37] P. Martinek, A simplified form of fuzzy multiset finite automata, in: R. Silhavy, R. Senkerik, Z. Kominkova Oplatkova, P. Silhavy, Z. Prokopova (Eds.), Artificial Intelligence Perspectives in Intelligent Systems, Proceedings of the 5th Computer Science On-line Conference 2016 (CSOC 2016), Vol. 1, Advances in Intelligent Systems and Computing, Vol. 464, Springer, Berlin, 2016, pp. 469–476. https://doi.org/10.1007/978-3-319-33625-1_42 [38] P. Martinek, Fuzzy multiset finite automata with output, Soft Comput. 26 (24) (2022) 13205–13217. https://doi.org/10.1007/s00500-022-07274-7
utb.fulltext.sponsorship	This research was supported by the Internal research project of the Faculty of Applied Informatics, Tomas Bata University in Zlin No. RVO/FAI/2024/004.
utb.wos.affiliation	[Martinek, Pavel] Tomas Bata Univ Zlin, Dept Math, Nam TG Masaryka 5555, Zlin 76001, Czech Republic
utb.scopus.affiliation	Martinek P., Department of Mathematics, Tomas Bata University in Zlín, nám. T. G. Masaryka 5555, 760 01 Zlín, Czech Republic
utb.fulltext.projects	RVO/FAI/2024/004
utb.fulltext.faculty	Faculty of Applied Informatics
utb.fulltext.ou	Department of Mathematics