Abstract
Inspired by the generalizations from grammars and finite automata to fuzzy grammars and fuzzy finite automata, respectively, we introduce the concepts of fuzzy multiset grammars and fuzzy multiset finite automata (FMFAs), as the generalizations of multiset grammars and multiset finite automata, respectively. The relationship between fuzzy multiset regular grammars and FMFAs is discussed. Furthermore, we define some operations on fuzzy multiset languages, and prove that the family of FMFA languages is closed under the operations.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
\(\widetilde{\delta }(A, 0_{\Sigma }, q_{F})=\mu _{\widetilde{G}}(A\rightarrow 0_{V}),\;{\text{where}} \;A\in V_{\rm N}.\)
\({\mu _{\widetilde{G}}(\langle A\rangle \rightarrow 0_{V})=\max \nolimits _{B\in Q}\{\widetilde{\delta }(A, 0_{\Sigma },B)\wedge \sigma _{1}(B)\}, \;{\text{where}}\;A, B\in Q.}\)
\(\mu _{\widetilde{G}}(\langle S\rangle \rightarrow 0_{V})=\max \nolimits _{A, B\in Q}\{\sigma _{0}(A)\wedge \widetilde{\delta }(A, 0_{\Sigma },B)\wedge \sigma _{1}(B)\},\; {\text{where}}\;A, B\in Q.\)
The case for \(m=1\) is that the sequence of states is empty.
References
Blizard WD (1989) Multiset theory. Notre Dame J Form Log 30(1):36–66
Blanchet-Sadri F, Morgan C (2001) Multiset and set decipherable codes. Comput Math Appl 41(10–11):1257–1262
Calude CS, Păun G, Rozenberg G, Salomaa A (eds) (2001) Multiset processing—mathematical, computer science and molecular computing points of view. Lecture Notes in Computer Science, vol 2235, Springer, Berlin
Cavaliere M, Freund R, Oswald M, Sburlan D (2007) Multiset random context grammars, checkers, and transducers. Theor Comput Sci 372(2–3):136–151
Casanovas J, Mayor G (2008) Discrete t-norms and operations on extended multisets. Fuzzy Sets Syst 159:1165–1177
Crespi-Reghizzi S, Mandrioli D (1976) Commutative grammars. Calcolo 13(2):173–189
Csuhaj-Varjú E, Martín-Vide C, Mitrana V (2001) Multiset automata. In: Calude CS, Păun G, Rozenberg G, Salomaa A (eds) Multiset processing—mathematical, computer science and molecular computing points of view. Springer, Berlin, pp 69–83
Frisch AM, Hnich B, Kiziltan Z, Miguel I, Walsh T (2009) Filtering algorithms for the multiset ordering constraint. Artif Intell 173(2):299–328
Hopcroft JE, Ullman JD (1979) Introduction to automata theory, languages and computation. Addison-Wesley, New York
Kudlek M, Martín-Vide C, Păun G (2001) Toward a formal macroset theory. In: Calude CS, Păun G, Rozenberg G, Salomaa A (eds) Multiset processing—mathematical, computer science and molecular computing points of view. Springer, Berlin, pp 123–133
Kudlek M, Totzke P, Zetzsche G (2009a) Multiset pushdown Automata. Fundam. Inform 93:221–233
Kudlek M, Mitrana V (2002) Closure Properties of Multiset Language Families. Fundam Inform 49:191–203
Kudlek M, Totzke P, Zetzsche G (2009b) Properties of multiset language classes defined by multiset pushdown automata. Fundam Inform 93:235–244
Li YM, Pedrycz W (2005) Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids. Fuzzy Sets Syst 156:68–92
Li ZH, Li P, Li YM (2006) The relationships among several types of fuzzy automata. Inform Sci 176(15):2208–2226
Li YM (2008) Approximation and robustness of fuzzy finite automata. Int J Approx Reasoning 47(2):247–257
Mordeson JN, Malik DS (2002) Fuzzy automata and languages: theory and applications. Chapman & Hall/CRC, London
Murthy VK, Krishnamurthy EV (1995) Probabilistic parallel programming based on multiset transformation. Future Gener Comput Syst 11(3):283–293
McGregor S (2008) Further results in multiset processing with neural networks. Neural Netw 21(6):830–837
Pedrycz W, Gacek A (2001) Learning of fuzzy automata. Int J Comput Intell Appl 1(1):19–33
Păun G, Rozenberg G, Salomaa A (1998) DNA computing: new computing paradigms. Springer, Berlin
Păun G, Pérez-Jiménez MJ (2006) Membrane computing: brief introduction, recent results and applications. Biosystems 85(1):11–22
Qiu DW (2006) Pumping lemma in automata theory based on complete residuated lattice-valued logic: a note. Fuzzy Sets Syst 157:2128–2138
Raymond D, Wood D, Yu S (1996) Automata Implementation. First International Workshop on Implementing Automata. Lecture Notes in Computer Science, vol 1260. Springer, Berlin
Salomaa A (1969) Theory of automata. Pergamon Press, Oxford
Santos ES (1968) Maximin automata. Inf Control 12:367–377
Tauler R, Maeder M, Juan A (2009) Multiset data analysis: extended multivariate curve resolution. In: Brown SD, Tauler R, Walczak B (eds) Comprehensive chemometrics: chemical and biochemical data analysis. Elsevier, Oxford, pp 473–505
Wee WG (1967) On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification. PhD thesis, Purdue University
Wu QE, Wang T, Huang YX, Li JS (2009) State fusion of fuzzy automata with application on target tracking. Comput Math Appl 57(6):949–960
Yu S (1997) Regular languages. In: Rozenberg G, Salomaa A (eds) Handbook of formal languages. Springer, Berlin, pp 41–110
Zadeh LA (1965) Fuzzy sets. Inf Control 8:338–353
Acknowledgments
The work was fully supported by the National Natural Science Foundation of China under Grant Nos. 60803102, 61070084, National Key Basic Research Program of China (973 Program) under Grant No. 2012CB326403, Guangxi “Bagui Scholar” Teams for Innovation and Research, Natural Science Foundation of Jilin Province under Grant No.201215006, the Fundamental Research Funds for the Central Universities under Grant No. 11CXPY010, and Opening Fund of Top Key Discipline of Computer Software and Theory in Zhejiang Provincial Colleges at Zhejiang Normal University of China under Grant No.ZSDZZZZXK37.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, J., Yin, M. & Gu, W. Fuzzy multiset finite automata and their languages. Soft Comput 17, 381–390 (2013). https://doi.org/10.1007/s00500-012-0913-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-012-0913-6