Bisimulation for BL-general fuzzy automata

Document Type: Research Paper

Authors

1 Department of Mathematics, Graduate University of Advanced Technology, Kerman, Iran

2 Department of Mathematics, Kazerun Branch, Islamic Azad University, Kazerun, Iran

Abstract

In this note, we define bisimulation for BL-general fuzzy automata and show that if there is a bisimulation between two BL-general fuzzy automata, then they have the same behavior.
For a given BL-general fuzzy automata, we obtain the greatest bisimulation for the BL-general fuzzy automata. Thereafter, if we use the greatest bisimulation, then we obtain a quotient BL-general fuzzy automata and this quotient is minimal, furthermore there is a morphism from the first one to its quotient.
Also, for two given BL-general fuzzy automata we present an algorithm, which determines bisimulation between them.
Finally, we present some examples to clarify these new notions.

Keywords


[1] K. Abolpour and M. M. Zahedi, BL-general fuzzy automata and accept behavior, Journal
Applied Mathematics and Computing, 38 (2012), 103-118.
[2] K. Abolpour and M. M. Zahedi, Isomorphism between two BL-general fuzzy automata, Soft
Computing, 16 (2012), 729-736.
[3] C. Baier, B. Engelen and M. Majster Cederbaum, Deciding bisimilarity and similarity for
probabilistic processes, Journal of Computer and System Sciences, 60 (2000), 187-231.
[4] P. Buchholz, Bisimulation relations for weighted automata, Theoretical Computer Science,
393 (2008), 109-123.
[5] Y. Cao, G. Chen and E. Kerre, Bisimulations for fuzzy transition systems, IEEE Transactions
on Fuzzy Systems, 19 (2011), 540-552.
[6] Y. Cao, H. Wang, S. X. Sun and G. Chen, A behavioral distance for fuzzy-transition systems,
IEEE Transactions on Fuzzy Systems, 21 (2012), 735-747.
[7] M. Ciric, J. Ignjatovic, M. Basic and I. Jancic, Nondeterministic automata: equivalence,
bisimulations, and uniform relations, Information Sciences, 261 (2013), 185-218.
[8] M. Ciric, J. Ignjatovic, N. Damljanovic and M. Basic, Bisimulations for fuzzy automata,
Fuzzy Sets and Systems, 186 (2012) 100-139.
[9] M. Ciric, J. Ignjatovic, I. Jancic and N. Damljanovic, Computation of the greatest simulations
and bisimulations between fuzzy automata, Fuzzy Sets and Systems, 208 (2012), 22-42.
[10] N. Damljanovic, M. Ciric and J. Ignjatovic, Bisimulations for weighted automata over an
additively idempotent semiring, Theoretical Computer Science, 534 (2014), 86-100.
[11] W. Deng and D. W. Qiu, Supervisory control of fuzzy discrete event systems for simulation
equivalence, IEEE Transactions on Fuzzy Systems, 23 (2015), 178-192.
[12] M. Doostfatemeh and S. C. Kremer, New directions in fuzzy automata, International Journal
of Approximate Reasoning, 38 (2005), 175-214.
[13] C. L. Giles, C. W. Omlin and K. K. Thornber, Equivalence in knowledge representation:
automata, recurrent neural networks, and dynamical fuzzy systems, Proceedings of IEEE, 87
(1999), 1623-1640.
[14] M. M. Gupta, G. N. Saridis and B. R. Gaines, Fuzzy Automata and Decision Processes,
North Holland, New York, (1977), 111-175.
[15] P. Hajek, Metamathematics of fuzzy logic, Trends in Logic, Kluwer, Dordercht, 4 (1998).
[16] J. Hgberg, A. Maletti and J. May, Backward and forward bisimulation minimisation of tree
automata, In: J. Holub, J. drek (Eds.), IAA07, in: Lecture Notes in Computer Science, 4783
(2007), 109-121.

[17] J. Hgberg, A. Maletti and J. May, Backward and forward bisimulation minimisation of tree
automata, Theoretical Computer Science, 410 (2009) 3539-3552.
[18] D. C. Kozen, Automata and computability, Springer, USA, 1997.
[19] E. T. Lee and L. A. Zadeh, Note on fuzzy languages, Information Sciences, 1 (1969), 421-434.
[20] L. Li and D. Qiu, On the state minimization of fuzzy automata, IEEE Transactions on Fuzzy
Systems, 23 (2015), 434-443.
[21] N. Lynch and F. Vaandrager, Forward and backward simulations, Information and Computation,
121 (1995), 214-233.
[22] D. S. Malik and J. N. Mordeson, Fuzzy Automata and Languages: Theory and Applications,
Chapman Hall, CRC Boca Raton, London, New York, Washington DC, 2002.
[23] D. S. Malik and J. N. Mordeson, Fuzzy discrete structures, Physica-Verlag, New York, (2000),
London, 2002.
[24] R. Milner, Acalculus of communicating systems, In: G. Goos, J. Hartmanis (Eds.), Lecture
Notes in Computer Science, Springer, 92 (1980).
[25] C. W. Omlin, K. K. Thornber and C. L. Giles, Fuzzy nite-state automata can be deter-
ministically encoded in recurrent neural networks, IEEE Transactions on Fuzzy Systems, 5
(1998), 76-89.
[26] D. Park, Concurrency and automata on in nite sequences, In: P.Deussen(Ed.), Proceedings
of the 5th GI Conference, Karlsruhe, Germany, Lecture Notesin Computer Science, Springer-
Verlag, 104, (1981), 167-183.
[27] W. Pedrycz and A. Gacek, Learning of fuzzy automata, International Journal of Computational
Intelligence and Applications, 1 (2001), 19-33.
[28] K. Peeva, Behavior, reduction and minimization of nite L-automata, Fuzzy Sets and Systems,
28 (1988), 171-181.
[29] K. Peeva, Equivalence, reduction and minimization of nite automata over semirings, Theoretical
Computer Science, 88 (1991), 269-285.
[30] D. Qiu, Automata theory based on complete residuated lattice-valued logic, Science in China
Series: Information Sciences, 44 (2001), 419-429.
[31] D. Qiu, Automata theory based on complete residuated lattice-valued logic (II), Science in
China Series F: Information Sciences, 45 (2002), 442-452.
[32] D. Qiu, Characterizations of fuzzy nite automata, Fuzzy Sets and Systems, 141 (2004),
391-414.
[33] D. Qiu, Pumping lemma in automata theory based on complete residuated lattice-valued logic:
A not, Fuzzy Sets and Systems, 157 (2006), 2128-2138.
[34] D. Qiu, Supervisory control of fuzzy discrete event systems: a formal approach, IEEE Transactions
on Systems, Man and CyberneticsPart B, 35 (2005), 72-88.
[35] E. S. Santos, Maxmin automata, Information Control, 13 (1968), 363-377.
[36] V. Topencharov and K. Peeva, Equivalence, reduction and minimization of nite fuzzy au-
tomata, Journal of Mathematical Analysis and Applications, 84 (1981), 270-281.
[37] E. Turunen, Boolean deductive systems of BL-algebras, Archive for Mathematical Logic, 40
(2001), 467-473.
[38] W. G. Wee, On generalization of adaptive algorithm and application of the fuzzy sets concept
to pattern classi cation, Ph.D. Thesis, Purdue University, Lafayette, IN, 1967.
[39] W. G. Wee and K. S. Fu, A formulation of fuzzy automata and its application as a model of
learning systems, IEEE Transactions on Systems, Man and Cybernetics, 5 (1969), 215-223.
[40] L. Wu and D. Qiu, Automata theory based on complete residuated lattice-valued logic: Re-
duction and minimization, Fuzzy Sets and Systems, 161 (2010), 1635-1656.
[41] L. A. Zadeh, Fuzzy sets, Information and Control, 8 (1965,) 338-353.