Abstract
Weak bisimulations for fuzzy automata (FAs) are a well-known generalization of bisimulations. While they preserve the language equivalence between two FAs and perform better in the state reduction of FAs, their main disadvantage is that they cannot be computed for all \((\vee , \cdot )\)-FAs, where \(\vee \) denotes the maximum operation and \(\cdot \) is the product t-norm on the real-unit interval [0, 1]. The reason is that weak bisimulations are solutions to specific linear systems of fuzzy relation inequalities, and such systems can consist of infinitely many inequalities when observed under such FAs. This paper introduces new types of weak bisimulations for such FAs aiming to overcome this problem. Namely, for a chosen small value \(\varepsilon > 0\), we define \(\varepsilon \)-weak bisimulations. They allow us to obtain finite systems of fuzzy relation inequalities. They preserve a new kind of approximation of language equivalence. Namely, we show that two \((\vee , \cdot )\)-FAs that are \(\varepsilon \)-weak bisimilar recognize each word in degrees which are either equal or both less than or equal to \(\varepsilon \). As \(\varepsilon \)-weak bisimulations have this property for an arbitrarily small value \(\varepsilon > 0\), they model a kind of “almost-equivalence” between two FAs, as the words accepted in a degree smaller than or equal to \(\varepsilon \) can be treated as irrelevant.
I. Micić, J. Matejić and S. Stanimirović acknowledge the support of the Science Fund of the Republic of Serbia, GRANT No. 7750185, Quantitative Automata Models: Fundamental Problems and Applications - QUAM, and the Ministry of Education, Science and Technological Development, Republic of Serbia, Contract No. 451-03-68/2022-14/200124.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bělohlávek, R.: Fuzzy Relational Systems: Foundations and Principles. Kluwer, New York (2002)
Bělohlávek, R., Vychodil, V.: Fuzzy Equational Logic. Studies in Fuzziness and Soft Computing, Springer, Heidelberg (2005). https://doi.org/10.1007/b105121
Ćirić, M., Ignjatović, J., Damljanović, N., Bašić, M.: Bisimulations for fuzzy automata. Fuzzy Sets Syst. 186(1), 100–139 (2012)
Ćirić, M., Ignjatović, J., Jančić, I., Damljanović, N.: Computation of the greatest simulations and bisimulations between fuzzy automata. Fuzzy Sets Syst. 208, 22–42 (2012)
Jančić, I.: Weak bisimulations for fuzzy automata. Fuzzy Sets Syst. 249, 49–72 (2014)
Li, Y.: Approximation and robustness of fuzzy finite automata. Int. J. Approximate Reasoning 47(2), 247–257 (2008)
Micić, I., Jančić, Z., Stanimirović, S.: Computation of the greatest right and left invariant fuzzy quasi-orders and fuzzy equivalences. Fuzzy Sets Syst. 339, 99–118 (2018)
Micić, I., Nguyen, L.A., Stanimirović, S.: Characterization and computation of approximate bisimulations for fuzzy automata. Fuzzy Sets Syst. 442, 331–350 (2022)
Nguyen, L.: Computing crisp simulations for fuzzy labeled transition systems. J. Intell. Fuzzy Syst. 42(4), 3067–3078 (2022)
Nguyen, L., Tran, D.: Computing crisp bisimulations for fuzzy structures. CoRR abs/2010.15671 (2020)
Nguyen, L., Tran, D.: Computing fuzzy bisimulations for fuzzy structures under the Gödel semantics. IEEE Trans. Fuzzy Syst. 29(7), 1715–1724 (2021). https://doi.org/10.1109/TFUZZ.2020.2985000
Pan, H., Li, Y., Cao, Y., Li, P.: Nondeterministic fuzzy automata with membership values in complete residuated lattices. Int. J. Approximate Reasoning 82, 22–38 (2017)
Qiao, S., Zhu, P., Feng, J.E.: Fuzzy bisimulations for nondeterministic fuzzy transition systems. IEEE Trans. Fuzzy Syst. 31(7), 2450–2463 (2022). https://doi.org/10.1109/TFUZZ.2022.3227400
Stanimirović, S., Micić, I., Ćirić, M.: Approximate bisimulations for fuzzy automata over complete Heyting algebras. IEEE Trans. Fuzzy Syst. 30, 437–447 (2022)
Wu, H., Chen, T., Han, T., Chen, Y.: Bisimulations for fuzzy transition systems revisited. Int. J. Approximate Reasoning 99, 1–11 (2018)
Wu, H., Chen, Y., Bu, T., Deng, Y.: Algorithmic and logical characterizations of bisimulations for non-deterministic fuzzy transition systems. Fuzzy Sets Syst. 333, 106–123 (2018)
Yang, C., Li, Y.: Approximate bisimulation relations for fuzzy automata. Soft Comput. 22(14), 4535–4547 (2018). https://doi.org/10.1007/s00500-017-2913-z
Yang, C., Li, Y.: \(\epsilon \)-bisimulation relations for fuzzy automata. IEEE Trans. Fuzzy Syst. 26(4), 2017–2029 (2018)
Yang, C., Li, Y.: Approximate bisimulations and state reduction of fuzzy automata under fuzzy similarity measures. Fuzzy Sets Syst. 391, 72–95 (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Micić, I., Matejić, J., Stanimirović, S., Nguyen, L.A. (2023). Towards New Types of Weak Bisimulations for Fuzzy Automata Using the Product T-Norm. In: Massanet, S., Montes, S., Ruiz-Aguilera, D., González-Hidalgo, M. (eds) Fuzzy Logic and Technology, and Aggregation Operators. EUSFLAT AGOP 2023 2023. Lecture Notes in Computer Science, vol 14069. Springer, Cham. https://doi.org/10.1007/978-3-031-39965-7_47
Download citation
DOI: https://doi.org/10.1007/978-3-031-39965-7_47
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-39964-0
Online ISBN: 978-3-031-39965-7
eBook Packages: Computer ScienceComputer Science (R0)