Myhill-Nerode Fuzzy Congruences Corresponding to a General Fuzzy Automata

Subject Areas : Statistics

khadijeh abolpour ¹ , mohammad mehdi zahedi ² , marzieh shamsizadeh ³

1 - Dept. of Math., Shiraz Branch, Islamic Azad University, Shiraz, Iran
2 - Dept. of Math., Graduate University of Advanced Technology, Kerman, Iran
3 - Dept. of Math., Graduate University of Advanced Technology, Kerman, Iran

Received: 2019-07-16 Accepted : 2020-02-02 Published : 2020-08-22

Keywords: اتوماتای فازی عمومی, همنهشتی (مایهیل- نرود), مشبکه, تکواره, صریح,

Abstract :

Myhill-Nerode Theorem is regarded as a basic theorem in the theories of languages and automata and is used to prove the equivalence between automata and their languages. The significance of this theorem has stimulated researchers to develop that on different automata thus leading to optimizing computational models. In this article, we aim at developing the concept of congruence in general fuzzy automata on the basis of Myhill-Nerode. To do so, we first define general fuzzy automata induced by fuzzy right congruence using the concept of fuzzy right congruences on a free monoid. Further, using the concept of language identified by an automaton we will show that in this induced automaton there exists an identifiable language if and only if there is an extension from fuzzy right congruence on a free monoid. As a result, this identified language is equivalent to the crisp language of the very automaton. We also define Nerode fuzzy right congruence and Myhill fuzzy congruence with max-min general fuzzy automata showing that the language identified by general fuzzy automata max-min is equivalent to the language identified by max-min general fuzzy automata induced by Nerode fuzzy right congruence. Finally, we elaborate the concepts through examples.

References:

[1] Abolpour Kh., Zahedi M. M., "Isomorphism between two BL-general fuzzy automata", Soft Computing, 16 (2012) 729-736.

[2] Abolpour Kh., Zahedi M. M., "BL-general fuzzy automata and accept behavior",Journal of Applied Mathematics and Computing, 38 (2012) 103-118.

[3] Abolpour K., Zahedi M. M., "General Fuzzy Automata Based on Complete Residuated Lattice-Valued", Iranian Journal of Fuzzy Systems, 14 (2017) 103-121.

[4] Doostfatemeh M., Kremer S.C., "New directions in fuzzy automata", International Journal of Approximate Reasoning, 38 (2005) 175-214.

[5] Ignjatovic J., Ciric M., Bogdanovic S., Petkovic T., "Myhill-Nerode type theory for fuzzy languages and automata", Fuzzy Sets and Systems, (2009) 1-37.

[6] Maletti A., "Myhill-Nerode theorem for recognizable tree series revisited", in: E. S. Laber, et al. (Eds.) LATIN 2008, Lecture Notes in Computer Science, Vol. 4957, Springer, Heidelberg, 2008, pp. 106-120.

[7] Mordeson J.N., Malik D.S., "Fuzzy Automata and Languages, Theory and Applications", Chapman and Hall/CRC, London/Boca Raton, FL, 2002.

[8] Mordeson J.N., Nair P.S., "Fuzzy Mathematics, An Introduction for engineers and scientists", translated by R. Ameri, university of Mazandaran, Iran, 2003.

[9] Myhill J., "Finite automata and the representation of events", in: WADD TR-57-624, Wright Patterson AFB, Ohio, pp. 112-137.

[10] Nerode A., "Linear automata transformation", in: Proc. American Mathematical Society, Vol. 9, 1958, pp. 541-544.

[11] Santos E. S., "Fuzzy Automata and Languages, Information Sciences", 10 (1976) 193-197.  

[12] Shamsizadeh M., Zahedi M. M., Abolpour Kh., "Admissible partition for Bl-general fuzzy automaton", Iranian Journal of Fuzzy Systems, In Press.

[13] Shamsizadeh M., Zahedi M. M., Abolpour Kh., "Bisimulation for BL-general fuzzy automata", Iranian Journal of Fuzzy Systems, 13 (2016) 35-50.

[14] Steinby M., "Classifying regular languages by their syntactic algebras", in: Results and Trends in Theoretical Computer Science, Graz, 1994, Lecture Notes in Computer Sciences, Vol. 812, Springer, Berlin, 1994, pp. 396-409.

[15] Wee W.G., "On generalization of adaptive algorithm and application of the fuzzy sets   concept to pattern classification", Ph.D. Thesis, Purdue University, Lafayette, IN, 1967.

[16] Zadeh L .A., "Fuzzy sets", Inform. and Control, 8 (1965) 338-353.

[17] Zahedi M. M., Horry M., Abolpor Kh., "Bifuzzy (General) Topology on Max-Min General Fuzzy Automata ", Advances in Fuzz y Mathematics, Vol. 3, No. 1, (2008), 51-68.