IJMEMES logo

International Journal of Mathematical, Engineering and Management Sciences

ISSN: 2455-7749


State Minimization of General Finite Fuzzy Automata

State Minimization of General Finite Fuzzy Automata

Ranjeet Kaur
Department of Mathematics, Jaypee Institute of Information Technology, Noida, Uttar Pradesh, India. ABES Engineering College, Ghaziabad, Uttar Pradesh, India.

Alka Tripathi
Department of Mathematics, Jaypee Institute of Information Technology, Noida, Uttar Pradesh, India.

DOI https://doi.org/10.33889/IJMEMS.2021.6.6.101

Received on May 21, 2021
  ;
Accepted on November 11, 2021

Abstract

The minimization of automaton is important to reduce space and computational time. Reduction in number of states and transitions leads to equivalent automaton with less number of states and transitions. In this paper, state minimization of General Finite Fuzzy Automata (GFFA) is discussed. To obtain minimal equivalent GFFA we have removed redundant states and transitions using substitution property (SP) partition and quotient machine. The algorithm to find membership values of states of the GFFA is described and algorithm to associate states with quotient machine to obtain minimal machine with less number of states is discussed.

Keywords- General fuzzy automata, Minimal automata, Quotient machine, Substitution property partition.

Citation

Kaur, R., & Tripathi, A. (2021). State Minimization of General Finite Fuzzy Automata. International Journal of Mathematical, Engineering and Management Sciences, 6(6), 1709-1728. https://doi.org/10.33889/IJMEMS.2021.6.6.101.

Conflict of Interest

The authors confirm that there is no conflict of interest to declare for this publication

Acknowledgements

The authors are very grateful to the reviewers whose valuable remarks and suggestions that have made a significant contribution in improving the quality of the manuscript. This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

References

Abolpur, K., & Zahedi, M.M. (2012). Isomorphism between two BL-general fuzzy automata. Soft Computing, 16, 729-736. https://doi.org/10.1007/s00500-011-0782-4.

Bacon, G.C. (1964). The decomposition of stochastic automata. Information and Control, 7(3), 320-329. https://doi.org/10.1016/S0019-9958(64)90374-2.

Balle, B., & Rabusseau, G. (2020). Approximate minimization of weighted tree automata. Information and Computation. https://doi.org/10.1016/j.ic.2020.104654.

Basak, N.C., & Gupta, A. (2002). On quotient machines of a fuzzy automaton and the minimal machine. Fuzzy Sets and Systems, 125(2), 223-229. https://doi.org/10.1016/S0165-0114(01)00064-1.

Cheng, W., & Mo, Z. (2004). Minimization algorithm of fuzzy finite automata. Fuzzy Sets and Systems, 141(3), 439-448. https://doi.org/10.1016/S0165-0114(02)00607-3.

Choubey, A., & Ravi, K.M. (2013). Minimization of deterministic finite automata with vague (final) states and intuitionistic fuzzy (final) states. Iranian Journal of Fuzzy Systems, 10(1), 75-88.

Ciric, M., Stamenkovic, A., Ignjatovic, J., & Petkovic, T. (2010). Fuzzy relation equations and reduction of fuzzy automata. Journal of Computer and System Sciences, 76(7), 609-633.

Doostfatemeh, M., & Kremer, S.C. (2005). New directions in fuzzy automaton. International Journal of Approximate Reasoning, 38(2), 175-214. https://doi.org/10.1016/j.ijar.2004.08.001.

Doostfatemeh, M., & Kremer, S.C. (2006). General fuzzy automata, new efficient acceptors for fuzzy languages. IEEE International Conference on Fuzzy Systems (pp. 2097-2103). IEEE. Vancouver, BC, Canada. doi: 10.1109/FUZZY.2006.1681991.

Dubey, M.K., Tiwari, S.P., & Sostak, A. (2020). Categories of quantale-valued fuzzy automata: determinization and minimization. Journal of Applied Mathematics and Computing, 63, 771-785. https://doi.org/10.1007/s12190-020-01338-3.

Ghorani, M., & Moghari, S. (2021). Decidability of the minimization of fuzzy tree automata with membership values in complete lattices. Journal of Applied Mathematics and Computing. http://doi.org/10.1007/s12190-021-01529-6.

Horry, M., & Zahedi, M.M. (2013). Some (fuzzy) topologies on general fuzzy automata. Iranian Journal of Fuzzy Systems, 10(6), 73-89. https://dx.doi.org/10.22111/ijfs.2013.1317.

Ignjatovic, J., Ciric, M., & Jancic, Z. (2018). Weighted finite automata with output. Soft Computing, 22(4), 1121-1138. https://doi.org/10.1007/s00500-017-2493-y.

Kavikumar, J., Tiwari, S.P., Ebas, N.A., & Shamsidah, A.H.N. (2019). General fuzzy finite switchboard automata. New Mathematics and Natural Computation, 15(2), 283-305. https://doi.org/10.1142/S1793005719500157.

Lee, H.S. (2000). Minimizing fuzzy finite automata. Ninth IEEE International Conference on Fuzzy Systems (Vol. 1, pp. 65-70). IEEE. San Antonio, TX, USA. https://dx.doi.org/10.1109/FUZZY.2000.838635.

Li, L., & Qiu, D. (2015). On the state minimization of fuzzy automata. IEEE Transactions on Fuzzy Systems, 23(2), 434-443. https://doi.org/10.1109/TFUZZ.2014. 2315620.

Li, Y., & Pedrycz, W. (2007). Minimization of lattice finite automata and its application to the decomposition of lattice languages. Fuzzy Sets and Systems, 158(13), 1423-1436. http://dx.doi.org/10.1016/j.fss.2007.03.003.

Malik, D.S., Mordeson, J.N., & Sen, M.K. (1999). Minimization of fuzzy finite automata. Information Sciences, 113(3-4), 323-330. https://doi.org/10.1016/S0020-0255(98)10073-7.

Mendivil, J.R.G. (2018). Condition for minimal fuzzy deterministic finite automata via brzozowski’s procedure. IEEE Transactions on Fuzzy Systems, 26(4), 2409-2420. https://doi.org/10.1109/TFUZZ.2017.2775601.

Mizumoto, M., Toyoda, J., & Tanaka, K. (1969). Some considerations on fuzzy automata. Journal of Computer and System Sciences, 3(4), 409-422. https://doi.org/10.1016/S0022-0000(69)80029-2.

Peeva, K.G., & Zahariev, Z. (2008). Computing behavior of finite fuzzy machines-algorithm and its application to reduction and minimization. Information Sciences, 178(21), 4152-4165.

Santos, E.S. (1972). On reduction of maximin machines. Journal of Mathematical Analysis and Applications, 40(1), 60-78.

Shamsizadeh, M., & Zahedi, M.M. (2019). Bisimulation of type 2 for BL-general fuzzy automata. Soft Computing, 23, 9843-9852. https://doi.org/10.1007/s00500-019-03812-y.

Shamsizadeh, M., & Zahedi, M.M. (2015). Minimal intuitionistic general L-fuzzy automata. Italian Journal of Pure and Applied Mathematics, 35, 155-186.

Shamsizadeh, M., & Zahedi, M.M. (2016). Intuitionistic general fuzzy automata. Soft Computing, 20, 3505-3519. https://doi.org/10.1007/s00500-015-1969-x.

Stamenkovic, A., Ciric, M., & Basic, M. (2018). Ranks of fuzzy matrices. applications in state reduction of fuzzy automata. Fuzzy Sets and Systems, 333, 124-139. https://doi.org/10.1016/j.fss.2017.05.028.

Topencharov, V.V., & Peeva, K.G. (1981). Equivalence, reduction and minimization of finite fuzzy-automata. Journal of Mathematical Analysis and Applications, 84(1), 270-281.

Tripathi, A., & Kaur, R. (2019). A review of state minimization and state reduction techniques in fuzzy automata. AIP Conference Proceedings (Vol. 2061, No. 1, p. 020033). https://doi.org/10.1063/1.5086655.

Wee, W.G., & Fu, K.S. (1969). A formulation of fuzzy automata and its application as a model of learning systems. IEEE Transaction on Systems Science and Cybernetics, 5(3), 215-223, https://doi.org/10.1109/TSSC.1969.300263.

Wee, W.G. (1967). On generalizations of adaptive algorithm and application of fuzzy sets concept to pattern classification. Ph D. thesis, Purdue University.

Zadeh, L.A. (1965). Fuzzy sets. Information and Control, 8(3), 338-353. https://doi.org/10.1016/S0019-9958(65)90241-X.

Zhiwen, M., & Xiaolei, H. (2007). Minimization of mizumoto automata. Fuzzy Information and Engineering, 40, 739-743. https://doi.org/10.1007/978-3-540-71441-5_79.