×

Canonization of max-min fuzzy automata. (English) Zbl 1423.68253

Summary: In this paper, we propose a canonization method for fuzzy automata, i.e., a determinization method that is able to return a minimal fuzzy deterministic automaton equivalent to the original fuzzy automaton. The canonization method is derived from the well-known Brzozowski’s algorithm for ordinary nondeterministic automata. For a given fuzzy automaton \(A\), we prove that the construction \(\hat{M}(r(N(r(A))))\) returns a minimal fuzzy deterministic automaton equivalent to \(A\). In that construction, \(r(.)\) represents the reversal of a fuzzy automaton, \(N(.)\) is the determinization of a fuzzy automaton based on fuzzy accessible subset construction, and \(\hat{M}(.)\) is the determinization of a fuzzy automaton via factorization of fuzzy states which also includes a simple reduction of a particular case of proportional fuzzy states. The method is accomplished for fuzzy automata with membership values over the Gödel structure (also called max-min fuzzy automata). These fuzzy automata are always determinizable and have been proved useful in practical applications.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Astrain, J. J.; González de Mendívil, J. R.; Garitagoitia, J. R., Fuzzy automata with \(ε\)-moves compute fuzzy measures between strings, Fuzzy Sets Syst., 157, 1550-1559 (2006) · Zbl 1092.68051
[2] Bělohlávek, R., Fuzzy Relational Systems: Foundations and Principles (2002), Kluwer: Kluwer New York · Zbl 1067.03059
[3] Bělohlávek, R., Determinism and fuzzy automata, Inf. Sci., 143, 205-209 (2002) · Zbl 1018.68040
[4] Bozapalidis, S.; Louscou-Bozapalidou, O., On the recognizability of fuzzy languages I, Fuzzy Sets Syst., 157, 2394-2402 (2006) · Zbl 1106.68058
[5] Brzozowski, J. A., Canonical regular expressions and minimal state graphs for definite events, (Proc. Sympos. Math. Theory of Automata. Proc. Sympos. Math. Theory of Automata, New York, 1962 (1963), Polytechnic Press of Polytechnic Inst. of Brooklyn: Polytechnic Press of Polytechnic Inst. of Brooklyn Brooklyn, N.Y.), 529-561 · Zbl 0116.33605
[6] Dubois, D.; Prade, H., Fuzzy Sets and Systems: Theory and Applications (1980), Academic: Academic New York, NY, USA · Zbl 0444.94049
[7] Gonzalez de Mendivil, J. R., Conditions for minimal fuzzy deterministic finite automata via Brzozowski’s procedure, IEEE Trans. Fuzzy Syst. (2017)
[8] Gonzalez de Mendivil, J. R.; Garitagoitia, J. R., Determinization of fuzzy automata via factorization of fuzzy states, Inf. Sci., 283, 165-179 (2014) · Zbl 1355.68158
[9] Gonzalez de Mendivil, J. R.; Garitagoitia, J. R., Fuzzy languages of infinite range: pumping lemmas and determinization procedure, Fuzzy Sets Syst., 249, 1-26 (2014) · Zbl 1334.68119
[10] Gupta, M. M.; Saridis, G. N.; Gaines, B. R., Fuzzy Automata and Decision Processes (1977), North-Holland: North-Holland New York · Zbl 0378.68035
[11] Hopcroft, J. E.; Motwani, R.; Ullman, J. D., Introduction to Automata Theory (2007), Addison-Wesley
[12] Ignjatović, J.; Ćirić, M.; Bogdanović, S., Determinization of fuzzy automata with membership values in complete residuated lattices, Inf. Sci., 178, 164-180 (2008) · Zbl 1128.68047
[13] Ignjatović, J.; Ćirić, M.; Bogdanović, S.; Petković, T., Myhill-Nerode type theory for fuzzy languages and automata, Fuzzy Sets Syst., 161, 1288-1324 (2010) · Zbl 1202.68261
[14] Jančić, Z.; Ignjatović, J.; Ćirić, M., An improved algorithm for determinization of weighted and fuzzy automata, Inf. Sci., 181, 1358-1368 (2011) · Zbl 1216.68144
[15] Jančić, Z.; Micić, I.; Ignjatović, J.; Ćirić, M., Further improvements of determinization methods for fuzzy finite automata, Fuzzy Sets Syst., 301, 79-102 (2016) · Zbl 1378.68105
[16] Jančić, Z.; Ćirić, M., Brzozowski type determinization for fuzzy automata, Fuzzy Sets Syst., 249, 73-82 (2014) · Zbl 1334.68121
[17] Lee, E. T.; Zadeh, L. A., Note on fuzzy languages, Inf. Sci., 1, 421-434 (1969)
[18] Li, Y. M.; Pedrycz, W., Fuzzy finite automata and fuzzy regular expressions with membership values in lattice ordered monoids, Fuzzy Sets Syst., 156, 68-92 (2005) · Zbl 1083.68059
[19] Micić, I.; Jančić, Z.; Ignjatović, J.; Ćirić, M., Determinization of fuzzy automata by means of degrees of language inclusion, IEEE Trans. Fuzzy Syst., 23, 6, 2144-2153 (2015)
[20] Mordeson, J.; Malik, D., Fuzzy Automata and Languages: Theory and Applications (2002), Chapman & Hall, CRC Press: Chapman & Hall, CRC Press London, Boca Raton, FL · Zbl 1046.68068
[21] Qiu, D. W., Automata theory based on complete residuated lattice-valued logic, Sci. China, Ser. F, 44, 6, 419-429 (2001) · Zbl 1125.68383
[22] Qiu, D. W., Automata theory based on complete residuated lattice-valued logic (II), Sci. China, Ser. F, 45, 6, 442-452 (2002) · Zbl 1161.68549
[23] Qiu, D. W., Supervisory control of fuzzy discrete event systems: a formal approach, IEEE Trans. Syst. Man Cybern., Part B, Cybern., 35, 1, 72-88 (2005)
[24] Sakarovitch, J., Elements of Automata Theory (2009), Cambridge University Press · Zbl 1188.68177
[25] Santos, E. S., Maxmin automata, Inform. Control, 13, 363-377 (1968) · Zbl 0174.03601
[26] Santos, E. S., On reductions of maxmin machines, J. Math. Anal. Appl., 40, 60-78 (1972) · Zbl 0245.94041
[27] Wee, W. G.; Fu, K. S., A formulation of fuzzy automata and its application as a model of learning systems, IEEE Trans. Syst. Man Cybern., SMC-5, 3, 215-223 (1969) · Zbl 0188.33203
[28] Li, L.; Qiu, D. W., On the state minimization of fuzzy automata, IEEE Trans. Fuzzy Syst., 23, 2, 434-443 (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.