×

Bisimulations for fuzzy automata. (English) Zbl 1237.68113

Summary: Bisimulations have been widely used in many areas of computer science to model equivalence between various systems, and to reduce the number of states of these systems, whereas uniform fuzzy relations have recently been introduced as a means to model the fuzzy equivalence between elements of two possible different sets. Here we use the conjunction of these two concepts as a powerful tool in the study of equivalence between fuzzy automata. We prove that a uniform fuzzy relation between fuzzy automata \(\mathcal A\) and \(\mathcal B\) is a forward bisimulation if and only if its kernel and co-kernel are forward bisimulation fuzzy equivalence relations on \(\mathcal A\) and \(\mathcal B\) and there is a special isomorphism between factor fuzzy automata with respect to these fuzzy equivalence relations. As a consequence we get that fuzzy automata \(\mathcal A\) and \(\mathcal B\) are UFB-equivalent, i.e., there is a uniform forward bisimulation between them, if and only if there is a special isomorphism between the factor fuzzy automata of \(\mathcal A\) and \(\mathcal B\) with respect to their greatest forward bisimulation fuzzy equivalence relations. This result reduces the problem of testing UFB-equivalence to the problem of testing isomorphism of fuzzy automata, which is closely related to the well-known graph isomorphism problem. We prove some similar results for backward-forward bisimulations, and we point to fundamental differences. Because of the duality with the studied concepts, backward and forward-backward bisimulations are not considered separately. Finally, we give a comprehensive overview of various concepts on deterministic, nondeterministic, fuzzy, and weighted automata, which are related to bisimulations.

MSC:

68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Software:

Stony Brook
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aceto, L.; Ingolfsdottir, A.; Larsen, K. G.; Srba, J., Reactive Systems: Modelling, Specification and Verification (2007), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1141.68043
[2] Bandler, W.; Kohout, L. J., On the general theory of relational morphisms, International Journal of General Systems, 13, 47-66 (1986) · Zbl 0875.04002
[3] Basak, N. C.; Gupta, A., On quotient machines of a fuzzy automaton and the minimal machine, Fuzzy Sets and Systems, 125, 223-229 (2002) · Zbl 1015.68130
[4] Béal, M. P.; Lombardy, S.; Sakarovitch, J., On the equivalence of Z-automata, (Caires, L.; etal., ICALP 2005, Lecture Notes in Computer Science, vol. 3580 (2005), Springer: Springer Heidelberg), 397-409 · Zbl 1082.68069
[5] Béal, M. P.; Lombardy, S.; Sakarovitch, J., Conjugacy and equivalence of weighted automata and functional transducers, (Grigoriev, D.; Harrison, J.; Hirsch, E. A., CSR 2006, Lecture Notes in Computer Science, vol. 3967 (2006), Springer: Springer Heidelberg), 58-69 · Zbl 1185.68381
[6] Béal, M. P.; Perrin, D., On the generating sequences of regular languages on \(k\) symbols, Journal of the ACM, 50, 955-980 (2003) · Zbl 1325.68125
[7] Bělohlávek, R., Fuzzy Relational Systems: Foundations and Principles (2002), Kluwer: Kluwer New York · Zbl 1067.03059
[8] Bělohlávek, R., Determinism and fuzzy automata, Information Sciences, 143, 205-209 (2002) · Zbl 1018.68040
[9] Bělohlávek, R.; Vychodil, V., Fuzzy Equational Logic, Studies in Fuzziness and Soft Computing (2005), Springer: Springer Berlin-Heidelberg · Zbl 1083.03030
[10] Bloom, S. L.; Ésik, Z., Iteration Theories: The Equational Logic of Iterative Processes, EATCS Monographs on Theoretical Computer Science (1993), Springer: Springer Berlin-Heilderberg · Zbl 0796.68153
[11] Brihaye, T., Words and bisimulations of dynamical systems, Discrete Mathematics and Theoretical Computer Science, 9, 2, 11-32 (2007) · Zbl 1152.68470
[12] Buchholz, P., Bisimulation relations for weighted automata, Theoretical Computer Science, 393, 109-123 (2008) · Zbl 1136.68032
[13] Calude, C. S.; Calude, E.; Khoussainov, B., Finite nondeterministic automata: Simulation and minimality, Theoretical Computer Science, 242, 219-235 (2000) · Zbl 0944.68098
[14] Champarnaud, J.-M.; Coulon, F., NFA reduction algorithms by means of regular inequalities, Theoretical Computer Science, 327, 241-253 (2004) · Zbl 1071.68039
[15] Cheng, W.; Mo, Z., Minimization algorithm of fuzzy finite automata, Fuzzy Sets and Systems, 141, 439-448 (2004) · Zbl 1069.68563
[16] Cho, S. J.; Kim, J. G.; Lee, W. S., Decompositions of T-generalized transformation semigroups, Fuzzy Sets and Systems, 122, 527-537 (2001) · Zbl 1066.68083
[17] Ćirić, M.; Droste, M.; Ignjatović, J.; Vogler, H., Determinization of weighted finite automata over strong bimonoids, Information Sciences, 180, 3497-3520 (2010) · Zbl 1205.68198
[18] Ćirić, M.; Ignjatović, J.; Bogdanović, S., Fuzzy equivalence relations and their equivalence classes, Fuzzy Sets and Systems, 158, 1295-1313 (2007) · Zbl 1123.03049
[19] Ćirić, M.; Ignjatović, J.; Bogdanović, S., Uniform fuzzy relations and fuzzy functions, Fuzzy Sets and Systems, 160, 1054-1081 (2009) · Zbl 1188.03035
[20] Ćirić, M.; Stamenković, A.; Ignjatović, J.; Petković, T., Factorization of fuzzy automata, (Csuhaj-Varju, E.; Ésik, Z., FCT 2007, Lecture Notes in Computer Science, vol. 4639 (2007), Springer: Springer Heidelberg), 213-225 · Zbl 1135.68452
[21] Ćirić, M.; Stamenković, A.; Ignjatović, J.; Petković, T., Fuzzy relation equations and reduction of fuzzy automata, Journal of Computer and System Sciences, 76, 609-633 (2010) · Zbl 1197.68051
[22] Demirci, M., Fuzzy functions and their applications, Journal of Mathematical Analysis and Applications, 252, 495-517 (2000) · Zbl 0973.03071
[23] Demirci, M., Foundations of fuzzy functions and vague algebra based on many-valued equivalence relations, part I: fuzzy functions and their applications, International Journal of general Systems, 32, 2, 123-155 (2003) · Zbl 1028.03044
[24] Demirci, M., A theory of vague lattices based on many-valued equivalence relations - I: general representation results, Fuzzy Sets and Systems, 151, 437-472 (2005) · Zbl 1067.06006
[25] Dubois, D.; Prade, H., Fuzzy Sets and Systems: Theory and Applications (1980), Academic Press: Academic Press New York · Zbl 0444.94049
[26] Ésik, Z.; Kuich, W., A generalization of Kozen’s axiomatization of the equational theory of the regular sets, (Words Semigroups and Transductions (2001), World Scientific: World Scientific River Edge, NJ), 99-114 · Zbl 1499.68207
[27] Z. Ésik, A. Maletti, Simulation vs. Equivalence, CoRR abs/1004.2426 (2010).; Z. Ésik, A. Maletti, Simulation vs. Equivalence, CoRR abs/1004.2426 (2010).
[28] Dovier, A.; Piazza, C.; Policriti, A., An efficient algorithm for computing bisimulation equivalence, Theoretical Computer Science, 311, 221-256 (2004) · Zbl 1070.68101
[29] Droste, M.; Stüber, T.; Vogler, H., Weighted finite automata over strong bimonoids, Information Sciences, 180, 156-166 (2010) · Zbl 1183.68337
[30] Droste, M.; Vogler, H., Kleene and Büchi results for weighted automata and multi-valued logics over arbitrary bounded lattices, (Gao, Y.; etal., 560 DLT 2010, Lecture Notes in Computer Science, vol. 6224 (2010)), 160-172 · Zbl 1250.03063
[31] Eilenberg, S., Automata, Languages and Machines, vol. B (1976), Academic Press: Academic Press New York
[32] Gentilini, R.; Piazza, C.; Policriti, A., From bisimulation to simulation: coarsest partition problems, Journal of Automated Reasoning, 31, 73-103 (2003) · Zbl 1081.68052
[33] Gupta, M. M.; Saridis, G. N.; Gaines, B. R., Fuzzy Automata and Decision Processes (1977), North-Holland: North-Holland New York · Zbl 0378.68035
[34] Hájek, P., Mathematics of fuzzy logic (1998), Kluwer: Kluwer Dordrecht
[35] Henzinger, T. A.; Kopke, P. W.; Puri, A.; Varaiya, P., What’s decidable about hybrid automata?, Journal of Computer and System Sciences, 57, 94-124 (1998) · Zbl 0920.68091
[36] Högberg, J.; Maletti, A.; May, J., Backward and forward bisimulation minimisation of tree automata, (Holub, J.; Ždárek, J., IAA07, Lecture Notes in Computer Science, vol 4783 (2007), Springer: Springer Heidelberg), 109-121 · Zbl 1139.68363
[37] Högberg, J.; Maletti, A.; May, J., Backward and forward bisimulation minimisation of tree automata, Theoretical Computer Science, 410, 3539-3552 (2009) · Zbl 1194.68139
[38] Höhle, U., Commutative residuated \(\ell \)-monoids, (Höhle, U.; Klement, E. P., Non-Classical Logics and Their Applications to Fuzzy Subsets (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, Dordrecht), 53-106 · Zbl 0838.06012
[39] Ignjatović, J.; Ćirić, M., Formal power series and regular operations on fuzzy languages, Information Sciences, 180, 1104-1120 (2010) · Zbl 1187.68323
[40] Ignjatović, J.; Ćirić, M.; Bogdanović, S., Determinization of fuzzy automata with membership values in complete residuated lattices, Information Sciences, 178, 164-180 (2008) · Zbl 1128.68047
[41] Ignjatović, J.; Ćirić, M.; Bogdanović, S., Fuzzy homomorphisms of algebras, Fuzzy Sets and Systems, 160, 2345-2365 (2009) · Zbl 1187.08002
[42] Ignjatović, J.; Ćirić, M.; Bogdanović, S., On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations, Fuzzy Sets and Systems, 161, 3081-3113 (2010) · Zbl 1231.03044
[43] Ignjatović, J.; Ćirić, M.; Bogdanović, S.; Petković, T., Myhill-Nerode type theory for fuzzy languages and automata, Fuzzy Sets and Systems, 161, 1288-1324 (2010) · Zbl 1202.68261
[44] Ilie, L.; Yu, S., Algorithms for computing small NFAs, (Diks, K.; etal., MFCS 2002, Lecture Notes in Computer Science, vol. 2420 (2002)), 328-340 · Zbl 1014.68082
[45] Ilie, L.; Yu, S., Reducing NFAs by invariant equivalences, Theoretical Computer Science, 306, 373-390 (2003) · Zbl 1059.68064
[46] Ilie, L.; Navarro, G.; Yu, S., On NFA reductions, (Karhumäki, J.; etal., Theory is Forever, Lecture Notes in Computer Science, vol. 3113 (2004)), 112-124 · Zbl 1055.68545
[47] Ilie, L.; Solis-Oba, R.; Yu, S., Reducing the size of NFAs by using equivalences and preorders, (Apostolico, A.; Crochemore, M.; Park, K., CPM 2005, Lecture Notes in Computer Science, vol. 3537 (2005)), 310-321 · Zbl 1131.68470
[48] Jančić, Z.; Ignjatović, J.; Ćirić, M., An improved algorithm for determinization of weighted and fuzzy automata, Information Sciences, 181, 1358-1368 (2011) · Zbl 1216.68144
[49] Kannellakis, P. C.; Smolka, S. A., CCS expressions, finite state processes, and three problems of equivalence, Information and Computation, 86, 43-68 (1990) · Zbl 0705.68063
[50] Kim, E.; Kohout, L. J., Generalized morphisms, a new tool for comparative evaluation of performance of fuzzy implications t-norms and co-norms in relational knowledge elicitation, Fuzzy Sets and Systems, 117, 297-315 (2001) · Zbl 0982.03031
[51] Kim, Y. H.; Kim, J. G.; Cho, S. J., Products of T-generalized state machines and T-generalized transformation semigroups, Fuzzy Sets and Systems, 93, 87-97 (1998) · Zbl 0928.68079
[52] Klawonn, F., Fuzzy points, fuzzy relations and fuzzy functions, (Novâk, V.; Perfilieva, I., Discovering World with Fuzzy Logic (2000), Physica-Verlag: Physica-Verlag Heidelberg), 431-453 · Zbl 1010.03045
[53] Klir, G. J.; Yuan, B., Fuzzy Sets and Fuzzy, Logic Theory and Application (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0915.03001
[54] Konstantinidis, S.; Santean, N.; Yu, S., Fuzzification of rational and recognizable sets, Fundamenta Informaticae, 76, 413-447 (2007) · Zbl 1123.68061
[55] Kozen, D. C., Automata and Computability (1997), Springer · Zbl 0883.68055
[56] Kumbhojkar, H. V.; Chaudhari, S. R., On covering of products of fuzzy finite state machines, Fuzzy Sets and Systems, 125, 215-222 (2002) · Zbl 1015.68129
[57] Kupferman, O.; Lustig, Y., Lattice automata, (Proceedings of VWCAI2007, Lecture Notes in Computer Science, vol. 4349 (2007)), 199-213 · Zbl 1132.68455
[58] Lee, E. T.; Zadeh, L. A., Note on fuzzy languages, Information Sciences, 1, 421-434 (1969)
[59] Lei, H.; Li, Y. M., Minimization of states in automata theory based on finite lattice-ordered monoids, Information Sciences, 177, 1413-1421 (2007) · Zbl 1109.68058
[60] Li, P.; Li, Y. M., Algebraic properties of LA-languages, Information Sciences, 176, 3232-3255 (2006) · Zbl 1110.68078
[61] Li, Y. M., Finite automata theory with membership values in lattices, Information Sciences, 181, 1003-1017 (2011) · Zbl 1209.68302
[62] 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
[63] 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
[64] Li, Z.; Li, P.; Li, Y. M., The relationships among several types of fuzzy automata, Information Sciences, 176, 2208-2226 (2006) · Zbl 1110.68065
[65] Lin, F.; Ying, H., Modeling and control of fuzzy discrete event systems, IEEE Transactions on Man Systems and Cybernetics - Part B, 32, 408-415 (2002)
[66] Lombardy, S., On the construction of reversible automata for reversible languages, (Widmayer, P.; etal., ICALP 2002, Lecture Notes in Computer Science, vol. 2380 (2002), Springer: Springer Heidelberg), 170-182 · Zbl 1056.68097
[67] Lombardy, S.; Sakarovitch, J., Derivatives of rational expressions with multiplicity, Theoretical Computer Science, 332, 141-177 (2005) · Zbl 1070.68074
[68] Lynch, N.; Vaandrager, F., Forward and backward simulations: part I. Untimed systems, Information and Computation, 121, 214-233 (1995) · Zbl 0834.68123
[69] Malik, D. S.; Mordeson, J. N.; Sen, M. K., Products of fuzzy finite state machines, Fuzzy Sets and Systems, 92, 95-102 (1997) · Zbl 0935.68064
[70] Malik, D. S.; Mordeson, J. N.; Sen, M. K., Minimization of fuzzy finite automata, Information Sciences, 113, 323-330 (1999) · Zbl 0948.68110
[71] Milner, R., A calculus of communicating systems, (Goos, G.; Hartmanis, J., Lecture Notes in Computer Science, vol. 92 (1980), Springer) · Zbl 0452.68027
[72] Milner, R., Communication and Concurrency (1989), Prentice-Hall International · Zbl 0683.68008
[73] Milner, R., Communicating and Mobile Systems: The \(\pi \)-Calculus (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0942.68002
[74] 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
[75] Paige, R.; Tarjan, R. E., Three partition refinement algorithms, SIAM Journal of Computing, 16, 973-989 (1987) · Zbl 0654.68072
[76] Park, D., Concurrency and automata on infinite sequences, (Deussen, P., Proceedings of the 5th GI Conference, Karlsruhe, Germany, Lecture Notes in Computer Science, vol. 104 (1981), Springer-Verlag), 167-183
[77] Peeva, K., Finite L-fuzzy acceptors, regular L-fuzzy grammars and syntactic pattern recognition, International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 12, 89-104 (2004) · Zbl 1074.68032
[78] Peeva, K., Finite L-fuzzy machines, Fuzzy Sets and Systems, 141, 415-437 (2004) · Zbl 1059.68066
[79] Peeva, K.; Kyosev, Y., Fuzzy Relational Calculus: Theory Applications, and Software (with CD-ROM), Advances in Fuzzy Systems - Applications and Theory, vol. 22, ((2004), World Scientific)
[80] Peeva, K.; Zahariev, Z., Computing behavior of finite fuzzy machines – algorithm and its application to reduction and minimization, Information Sciences, 178, 4152-4165 (2008) · Zbl 1170.68506
[81] Petković, T., Congruences and homomorphisms of fuzzy automata, Fuzzy Sets and Systems, 157, 444-458 (2006) · Zbl 1083.68073
[82] Pin, J. E., Syntactic semigroups, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 1 (1997), Springer: Springer Berlin-Heidelberg), 679-746
[83] Qiu, D. W., Automata theory based on completed residuated lattice-valued logic (I), Science in China (Ser. F), 44, 6, 419-429 (2001) · Zbl 1125.68383
[84] Qiu, D. W., Automata theory based on completed residuated lattice-valued logic (II), Science in China (Ser. F), 45, 6, 442-452 (2002) · Zbl 1161.68549
[85] Qiu, D. W., Characterizations of fuzzy finite automata, Fuzzy Sets and Systems, 141, 391-414 (2004) · Zbl 1059.68069
[86] Qiu, D. W., Supervisory control of fuzzy discrete event systems: a formal approach, IEEE Transactions on Systems, Man and Cybernetics - Part B, 35, 72-88 (2005)
[87] Qiu, D. W., Pumping lemma in automata theory based on complete residuated lattice-valued logic: a note, Fuzzy Sets and Systems, 157, 2128-2138 (2006) · Zbl 1121.03048
[88] Qiu, D. W., A note on Trillas’ CHC models, Artificial Intelligence, 171, 239-254 (2007) · Zbl 1168.06302
[89] Qiu, D. W.; Liu, F. C., Fuzzy discrete-event systems under fuzzy observability and a test algorithm, IEEE Transactions on Fuzzy Systems, 17, 3, 578-589 (2009)
[90] Ranzato, F.; Tapparo, F., Generalizing the Paige-Tarjan algorithm by abstract interpretation, Information and Computation, 206, 620-651 (2008) · Zbl 1197.68054
[91] Roggenbach, M.; Majster-Cederbaum, M., Towards a unified view of bisimulation: a comparative study, Theoretical Computer Science, 238, 81-130 (2000) · Zbl 0944.68136
[92] Rutten, J. J.M. M., Automata and coinduction (an exercise in coalgebra), (Sangiorgi, D.; de Simone, R., CONCUR’98, Lecture Notes in Computer Science, vol. 1466 (1998), Springer: Springer Heidelberg), 193-217 · Zbl 0940.68085
[93] Sakarovitch, J., Elements of Automata Theory (2009), Cambridge University Press
[94] Sangiorgi, D., On the origins of bisimulation and coinduction, ACM Transactions on Programming Languages and Systems, 31, 4, 111-151 (2009)
[95] Santos, E. S., Maximin automata, Information and Control, 12, 367-377 (1968) · Zbl 0174.03601
[96] Santos, E. S., On reduction of max-min machines, Journal of Mathematical Analysis and Applications, 37, 677-686 (1972) · Zbl 0245.94040
[97] Santos, E. S., Fuzzy automata and languages, Information Sciences, 10, 193-197 (1976) · Zbl 0336.94040
[98] Schmidt, G., Homomorphism and isomorphism theorems generalized from a relational perspective, (Schmidt, R. A., RelMiCS/AKA 2006, Lecture Notes in Computer Science, vol. 4136 (2006), Springer: Springer Heidelberg), 328-342 · Zbl 1135.08002
[99] Skiena, S. S., The Algorithm Design Manual (2008), Springer: Springer London · Zbl 1149.68081
[100] A. Stamenković, M. Ćirić, J. Ignjatović, Reduction of fuzzy automata by means of fuzzy quasi-orders, Information Sciences, submitted for publication.; A. Stamenković, M. Ćirić, J. Ignjatović, Reduction of fuzzy automata by means of fuzzy quasi-orders, Information Sciences, submitted for publication. · Zbl 1341.68111
[101] Walicki, M.; Białasik, M., Categories of relational structures, (Presicce, F. P., Recent Trends in Algebraic Developments Techniques, WADT’97, Lecture Notes in Computer Science, vol. 1376 (1998), Springer), 418-433 · Zbl 0907.08002
[102] Wechler, W., The Concept of Fuzziness in Automata and Language Theory (1978), Akademie-Verlag: Akademie-Verlag Berlin · Zbl 0401.94048
[103] W. G. Wee, On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification, Ph.D. Thesis, Purdue University, June 1967.; W. G. Wee, On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification, Ph.D. Thesis, Purdue University, June 1967.
[104] Wee, W. G.; Fu, K. S., A formulation of fuzzy automata and its application as a model of learning systems, IEEE Transactions on Systems, Man and Cybernetics, 5, 215-223 (1969) · Zbl 0188.33203
[105] Wu, L. H.; Qiu, D. W., Automata theory based on complete residuated lattice-valued logic: reduction and minimization, Fuzzy Sets and Systems, 161, 1635-1656 (2010) · Zbl 1192.68426
[106] Xing, H.; Qiu, D. W., Pumping lemma in context-free grammar theory based on complete residuated lattice-valued logic, Fuzzy Sets and Systems, 160, 1141-1151 (2009) · Zbl 1187.68305
[107] Xing, H.; Qiu, D. W., Automata theory based on complete residuated lattice-valued logic: a categorical approach, Fuzzy Sets and Systems, 160, 2416-2428 (2009) · Zbl 1181.18001
[108] Xing, H.; Qiu, D. W.; Liu, F. C., Automata theory based on complete residuated lattice-valued logic: pushdown automata, Fuzzy Sets and Systems, 160, 1125-1140 (2009) · Zbl 1182.68108
[109] Xing, H.; Qiu, D. W.; Liu, F. C.; Fan, Z. J., Equivalence in automata theory based on complete residuated lattice-valued logic, Fuzzy Sets and Systems, 158, 1407-1422 (2007) · Zbl 1152.68463
[110] Yeh, R. T., On relational homomorphisms of automata, Information and Control, 12, 140-155 (1968) · Zbl 0167.27503
[111] R. T. Yeh, Toward an algebraic theory of fuzzy relational systems, Technical Report: CS-TR-73-25, University of Texas at Austin, 1973.; R. T. Yeh, Toward an algebraic theory of fuzzy relational systems, Technical Report: CS-TR-73-25, University of Texas at Austin, 1973.
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.