Fuzzification of Rational and Recognizable Sets

• Autorzy: Konstantinidis S. , Nicolae S. , Yu S
• Języki publikacji: EN

Abstrakty

EN

In this paper we present a different framework for the study of fuzzy finite machines and their fuzzy languages. Unlike the previous work on fuzzy languages, characterized by fuzzification at the level of their acceptors/generators, here we follow a top-down approach by starting our fuzzification with more abstract entities: monoids and particular families in monoids. Moreover, we replace the unit interval (in fact, a finite subset of the unit interval) as support for fuzzy values with the more general structure of a lattice. We have found that completely distributive complete lattices allow the fuzzification at the highest level, that of recognizable and rational sets. Quite surprisingly, the fuzzification process has not followed thoroughly the classical (crisp) theory. Unlike the case of rational sets, the fuzzification of recognizable sets has revealed a few remarkable exceptions from the crisp theory: for example the difficulty of proving closure properties with respect to complement, meet and inverse morphisms. Nevertheless, we succeeded to prove the McKnight and Kleene theorems for fuzzy sets by making the link between fuzzy rational/recognizable sets on the one hand and fuzzy regular languages and FT-NFA languages (languages defined by NFA with fuzzy transitions) on the other. Finally, we have drawn the attention to fuzzy rational transductions, which have not been studied extensively and which bring in a strong note of applicability.

Słowa kluczowe

EN

fuzzy transducer; rational set; recognizable set; lattice

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 4
• Strony: 413--447
• Opis fizyczny: bibliogr. 39 poz.

Twórcy

autor

Konstantinidis S.

autor

Nicolae S.

autor

Yu S

• School of Computer Science, University of Waterloo, Waterloo N2L 3GI, ON Canada,

Bibliografia

• [1] Bělohlávek, R.: Determinism and Fuzzy Automata, Information Sciences, 143, 2002, 205-209.
• [2] Berstel, J.: Transductions and Context-Free Languages, B. G. Teubner, Stuttgart, 1979.
• [3] Berstel, J., Perrin, D.: Theory of Codes, Academic Press Inc., New York and London, 1985.
• [4] Berstel, J., Reutenauer, C.: Rational Series and their Languages, EATCS Monographs in Theoretical Computer Science, 12, 1988.
• [5] Birkhoff, G.: Lattice Theory - 2nd edition, vol. 25, AmericanMathematical Society Colloquium Publications, New York, 1948.
• [6] Book, R., Even, S., Greibach, S., Ott, G.: Ambiguity in Graphs and Expressions, IEEE Transactions on Computers, C-20(2), 1971, 149-153.
• [7] Dubois, D., Prade, H.: Fuzzy Sets and Systems: Theory and Applications, Academic Press, New York, London, 1980.
• [8] Eilenberg, S.: Algèbre Catégorique et Théorie des Automates, Institut H. Poincaré, Université de Paris, 1967.
• [9] Eilenberg, S.: Automata, Languages and Machines, vol. A, Academic Press, New York and London, 1974.
• [10] Goguen, J. A.: L-Fuzzy Sets, Journal of Mathematical Analysis and Applications, 18, 1967, 145-174.
• [11] 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, 1998, 87-97.
• [12] Kumbhojkar, H. V., Chaudhari, S. R.: Fuzzy Recognizers and Recognizable Sets, Fuzzy Sets and Systems, 131, 2002, 381-392.
• [13] Kumbhojkar, H. V., Chaudhari, S. R.: On Covering of Products of Fuzzy Finite State Machines, Fuzzy Sets and Systems, 125, 2002, 215-222.
• [14] Lee, E. T., Zadeh, L. A.: Note on Fuzzy Languages, Information Sciences, 1, 1969, 421-434.
• [15] Li, Y., Pedrycz, W.: Fuzzy Finite Automata and Fuzzy Regular Expressions with Membership Values in Lattice-Ordered Monoids, Fuzzy Sets and Systems, 156, 2005, 68-92.
• [16] Malik, D. S., Mordeson, J. N., Sen, M. K.: Products of Fuzzy Finite State Machines, Fuzzy Sets and Systems, 92, 1997, 95-102.
• [17] Mateescu, A., Salomaa, A., Yu, S.: Fuzzy Automata in Lexical Analysis, Journal of Universal Computer Science, 1(5), 1995, 292-311.
• [18] Mizumoto, M., , Tanaka, K.: Fuzzy-Fuzzy Automata, Kybernetes, 5, 1976, 107-112.
• [19] Mizumoto, M., Toyoda, J., Tanaka, K.: Some Considerations on Fuzzy Automata, Journal of Computer and Systems Sciences, 3, 1969, 409-442.
• [20] Mizumoto, M., Toyoda, J., Tanaka, K.: B-Fuzzy Grammars, International Journal of Computer Mathematics, 4(Sect. A), 1975, 343-368.
• [21] Moěkoř, J.: Fuzzy and non-Deterministic Automata, Soft Computing, 3, 1999, 221-226.
• [22] Moěkoř, J.: Semigroup Homomorphisms and Fuzzy Automata, Soft Computing, 6, 2002, 422-427.
• [23] Peeva, K.: Equivalence, Reduction and Minimization of Finite Automata over Semirings, Theoretical Computer Science, 88, 1991, 269-285.
• [24] Peeva, K., Topencharov, V.: Equivalence, Reduction and Minimization of Finite Fuzzy Automata, Journal of Mathematical Analysis and Applications, 84, 1981, 270-281.
• [25] Raney, G.: Completely Distributive Complete Lattices, Proceedings of the American Mathematical Society, 3, 1952, 667-680.
• [26] Sakarovitch, J.: éléments de Théorie des Automates, Vuibert Informatique, Paris, 2003.
• [27] Salomaa, A., Soittola, M.: Automata-Teoretic Aspects of Formal Power Series, Springer-Verlag, New York Heidelberg Berlin, 1978.
• [28] Santos, E. S.: Maximin Automata, Information and Control, 13, 1968, 363-377.
• [29] Santos, E. S.: Maximin Sequential-Like Machines and Chains, Mathematical Systems Theory, 3(4), 1969, 300-309.
• [30] Santos, E. S.: On Reductions of Maximin Machines, Journal of Mathematical Analysis and Applications, 40, 1972, 60-78.
• [31] Santos, E. S.: Regular Fuzzy Expressions, Fuzzy Automata and Decision Processes (M. M. Gupta, G. N. Saridis, B. R. Gaines, Eds.), North-Holland Publishing Co., 1977, 169-175.
• [32] Santos, E. S., Wee, W. G.: General Formulation of Sequential Machines, Information and Control, 12, 1968, 5-10.
• [33] Schützenberger, M.-P.: On the Definition of a Family of Automata, Information and Control, 4, 1961, 245-270.
• [34] Smolıková, R.: Some Properties of Fuzzy Automata, Bulletin sur les Sous-Ensembles Flous et leurs Applications (BUSEFAL), 63, 1995, 37-41.
• [35] Wechler, W.: R-Fuzzy Automata with a Time-Variant Structure, Mathematical Foundations of Computer Science, 3rd Symposium at Jadwisin, Poland (A. Blikle, Ed.), Lecture Notes in Computer Science, vol. 28 of Lecture Notes in Computer Science, Springer-Verlag, 1975, 73-76.
• [36] Wechler, W., Dimitrov, V.: R-Fuzzy Automata, Information Processing 74, Proceedings of IFIP Congress, Stockholm, Sweden (J. L. Rosenfeld, Ed.), North-Holland Publishing Co., 1974, 657-660.
• [37] Wee,W. G.: On Generalization of Adaptive Algorithms and Applications of the Fuzzy Sets Concept to Pattern Classification, Ph.D. Thesis, TR-EE 67/7, Purdue University, Lafayette, Indiana, 1967.
• [38] Wee,W. G., Fu, K. S.: A Formulation of Fuzzy Automata and its Application as aModel of Learning System, IEEE Transactions on System Science and Cybernetics, ssc-5(3), 1969, 215-223.
• [39] Zadeh, L. A.: Fuzzy Sets, Information and Control, 8, 1965, 338-353.