Finite automata theory with membership values in lattices. (English) Zbl 1209.68302
Summary: We study finite automata with membership values in a lattice, which are called lattice-valued finite automata. The extended subset construction of lattice-valued finite automata is introduced, then the equivalences between lattice-valued finite automata, lattice-valued deterministic finite automata and lattice-valued finite automata with \(\varepsilon \)-moves are proved. A simple characterization of lattice-valued languages recognized by lattice-valued finite automata is given, then it is proved that the Kleene theorem holds in the frame of lattice-setting. A minimization algorithm of lattice-valued deterministic finite automata is presented. In particular, the role of the distributive law for the truth valued domain of finite automata is analyzed: the distributive law is not necessary to many constructions of lattice-valued finite automata, but it indeed provides some convenience in simply processing lattice-valued finite automata.
References:
| [1] | Bělohlávek, R., Determinism and fuzzy automata, Information Sciences, 142, 205-209 (2002) · Zbl 1018.68040 |
| [2] | Birkhoff, G., Lattice Theory (1973), Amer. Math. Soc.: Amer. Math. Soc. Providence, Rhode Island, USA · Zbl 0126.03801 |
| [3] | Chechik, M.; Devereux, B.; Gurfinkel, A.; Easterbrook, S., Multi-valued symbolic model-checking, ACM Transactions on Software Engineering and Methodology, 12, 4, 1-38 (2004) |
| [4] | Droste, M.; Gastin, P., Weighted automata and weighted logics, Theoretical Computer Science, 380, 69-86 (2007) · Zbl 1118.68076 |
| [5] | Eilenberg, S., Automata, Languages and Machines, vols. A, B (1974), Academic Press: Academic Press New York · Zbl 0317.94045 |
| [6] | Gama, C. A.; Evsukoff, A. G.; Weber, P.; Ebecken, N. F.F., Parameter identification of recurrent fuzzy systems with fuzzy finite-state automata representation, IEEE Transactions on Fuzzy Systems, 16, 1, 213-224 (2008) |
| [7] | Gupta, M. M.; Saridis, G. N., Fuzzy Automata and Decision Processes (1977), North-Holland: North-Holland New York · Zbl 0378.68035 |
| [8] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley New York · Zbl 0196.01701 |
| [9] | Ignjatović, J.; Ćirić, M., Formal power series and regular operations on fuzzy languages, Information Sciences, 180, 7, 1104-1120 (2010) · Zbl 1187.68323 |
| [10] | Ignjatović, J.; Ćirić, M.; Bogdanović, S., Determinization of fuzzy automata with membership values in complete residuated lattices, Information Sciences, 178, 1, 164-180 (2008) · Zbl 1128.68047 |
| [11] | Kalmbach, G., Orthomodular Lattices (1983), Academic Press: Academic Press London · Zbl 0512.06011 |
| [12] | Kleene, S. C., Representation of events in nerve nets and finite automata, (Shannon, C. E.; McCarthy, J., Automata Studies (1956), Princeton University Press: Princeton University Press Princeton, NJ), 3-42 |
| [13] | Kuich, W.; Rahonis, G., Fuzzy regular languages over finite and infinite words, Fuzzy Sets and Systems, 157, 1532-1549 (2006) · Zbl 1092.68053 |
| [14] | Kuich, W.; Salomaa, A., Semirings, Automata Languages, EATCS Monographs on Theoretical Computer Science, vol. 5 (1986), Springer-Verlag: Springer-Verlag Berlin/Heidelberg/New York/Tokyo · Zbl 0582.68002 |
| [15] | O. Kupferman, Y. Lustig, Lattice automata, in: Proceedings of VWCAI2007, LNCS, vol. 4349, 2007, pp. 199-213.; O. Kupferman, Y. Lustig, Lattice automata, in: Proceedings of VWCAI2007, LNCS, vol. 4349, 2007, pp. 199-213. |
| [16] | Lee, E. T.; Zadeh, L. A., Note on fuzzy languages, Information Sciences, 1, 421-434 (1969) |
| [17] | Li, Y. M.; Li, Z. H., Free semilattices and strongly free semilattices generated by partially ordered sets, Northeastern Mathematical Journal, 9, 3, 359-366 (1993) · Zbl 0805.06004 |
| [18] | Li, Y. M., Analysis of Fuzzy Systems (2005), Academic Press: Academic Press Beijing, (in Chinese) |
| [19] | Li, Y. M.; Pedrycz, W., Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids, Fuzzy Sets and Systems, 156, 68-92 (2005) · Zbl 1083.68059 |
| [20] | Li, Y. M.; Pedrycz, W., Minimization of lattice finite automata and its application to the decomposition of lattice languages, Fuzzy Sets and Systems, 158, 1423-1436 (2007) · Zbl 1123.68063 |
| [21] | Li, P.; Li, Y. M., Algebraic properties of LA-languages, Information Sciences, 176, 3232-3255 (2006) · Zbl 1110.68078 |
| [22] | Li, Z. H.; Li, P.; Li, Y. M., The relationships among several types of fuzzy automata, Information Sciences, 176, 2208-2226 (2006) · Zbl 1110.68065 |
| [23] | Mordeson, J. N.; Malik, D. S., Fuzzy Automata and Languages: Theory and Applications (2002), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton, London · Zbl 1046.68068 |
| [24] | Qiu, D. W., Automata theory based on complete residuated lattice-valued logic, Science in China Series F, 44, 6, 419-429 (2001) · Zbl 1125.68383 |
| [25] | Qiu, D. W., Automata theory based on complete residuated lattice-valued logic (II), Science in China Series F, 45, 6, 442-452 (2002) · Zbl 1161.68549 |
| [26] | Qiu, D. W., Pumping lemma in automata theory based on complete residuated lattice-valued logic, Fuzzy Sets and Systems, 157, 2128-2138 (2006) · Zbl 1121.03048 |
| [27] | Qiu, D. W., Automata theory based on quantum logic: reversibilities and pushdown automata, Theoretical Computer Science, 386, 38-56 (2007) · Zbl 1137.68036 |
| [28] | Qiu, D. W., Automata theory based on quantum logic: some characterizations, Information and Computation, 190, 179-195 (2007) · Zbl 1074.68020 |
| [29] | Qiu, D. W., Notes on automata theory based on quantum logic, Science in China Series F: Information Sciences, 50, 2, 154-169 (2007) · Zbl 1121.68068 |
| [30] | Rabin, M. O.; Scott, D., Finite automata and their decision problems, IBM Journal of Research and Development, 3, 114-125 (1959) · Zbl 0158.25404 |
| [31] | Schützenberger, M. P., On the definition of a family of automata, Information and Control, 4, 245-270 (1961) · Zbl 0104.00702 |
| [32] | Wechler, W., The Concept of Fuzzyiness in Automata and Language Theory (1978), Akademie-Verlag: Akademie-Verlag Berlin · Zbl 0401.94048 |
| [33] | Ying, M. S., A theory of computation based on quantum logic (I), Theoretical Computer Science, 344, 134-207 (2005) · Zbl 1079.68035 |
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.
