Fuzzy regular languages over finite and infinite words. (English) Zbl 1092.68053
Summary: We consider finite automata over semirings and quemirings accepting finite and infinite words, respectively. We obtain Kleene theorems for fuzzy languages consisting of finite and infinite words. Furthermore, we introduce regular fuzzy grammars and linear fuzzy systems and we show that both of them specify the class of recognizable fuzzy languages consisting of finite and infinite words.
References:
| [1] | R. Alur, D. Dill, Automata for modeling real-time systems, ICALP’90, Lecture Notes in Computer Science, vol. 443, Springer, Berlin, 1990, pp. 322-335.; R. Alur, D. Dill, Automata for modeling real-time systems, ICALP’90, Lecture Notes in Computer Science, vol. 443, Springer, Berlin, 1990, pp. 322-335. · Zbl 0765.68150 |
| [2] | Alur, R.; Dill, D., A theory of timed automata, Theoret. Comput. Sci., 129, 167-186 (2002) |
| [3] | Balbes, R.; Dwinger, P., Distributive Lattices (1974), University of Missouri Press: University of Missouri Press Columbia, MO · Zbl 0321.06012 |
| [4] | Bloom, S. L.; Ésik, Z., Iteration theories, EATCS Monographs on Theoretical Computer Science (1993), Springer: Springer Berlin · Zbl 0773.03033 |
| [5] | Bouyer, P.; Petit, A., A Kleene/Büchi-like theorem for clock languages, J. Automata Languages and Combinatorics, 7, 167-186 (2002) · Zbl 1031.68121 |
| [6] | Conway, J. H., Regular Algebra and Finite Machines (1971), Chapman & Hall: Chapman & Hall London · Zbl 0231.94041 |
| [7] | M. Droste, D. Kuske, Skew and infinitary formal power series, Lecture Notes in Computer Science, vol. 2719, Springer, Berlin, 2003, pp. 426-438.; M. Droste, D. Kuske, Skew and infinitary formal power series, Lecture Notes in Computer Science, vol. 2719, Springer, Berlin, 2003, pp. 426-438. · Zbl 1039.68065 |
| [8] | M. Droste, D. Kuske, Skew and infinitary formal power series, Theoret. Comput. Sci., to appear.; M. Droste, D. Kuske, Skew and infinitary formal power series, Theoret. Comput. Sci., to appear. · Zbl 1039.68065 |
| [9] | M. Droste, U. Püschmann, Weighted Büchi Automata, submitted for publication.; M. Droste, U. Püschmann, Weighted Büchi Automata, submitted for publication. |
| [10] | Eilenberg, S., Automata, Languages and Machines, vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045 |
| [11] | Elgot, C., Matricial theories, J. Algebra, 42, 391-422 (1976) · Zbl 0361.18004 |
| [12] | Z. Ésik, W. Kuich, On iteration semiring-semimodule pairs, to appear.; Z. Ésik, W. Kuich, On iteration semiring-semimodule pairs, to appear. · Zbl 1155.16035 |
| [13] | Z. Ésik, W. Kuich, A semiring-semimodule generalization of \(\operatorname{\Omega;} \); Z. Ésik, W. Kuich, A semiring-semimodule generalization of \(\operatorname{\Omega;} \) · Zbl 1161.68524 |
| [14] | Z. Ésik, W. Kuich, A semiring-semimodule generalization of \(\operatorname{\Omega;} \); Z. Ésik, W. Kuich, A semiring-semimodule generalization of \(\operatorname{\Omega;} \) · Zbl 1161.68524 |
| [15] | M. Goldstern, Vervollständigung von Halbringen, Diplomarbeit, Technische Universität Wien, 1985.; M. Goldstern, Vervollständigung von Halbringen, Diplomarbeit, Technische Universität Wien, 1985. |
| [16] | Krithivasan, K.; Sharda, K., Fuzzy \(\omega \)-automata, Inform. Sci., 138, 257-281 (2001) · Zbl 1004.68090 |
| [17] | Kuich, W., Semirings and formal power seriestheir relevance to formal languages and automata theory, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 1 (1997), Springer: Springer Berlin), 609-677, (Chapter 9) · Zbl 0866.68057 |
| [18] | W. Kuich, Conway semirings and skew formal power series, in: Z. Ésik, Z. Fülöp (Eds.), Proc. 11th Internat. Conf. Automata and Formal Languages, Institute of Informatics, University of Szeged, 2005, pp. 164-177.; W. Kuich, Conway semirings and skew formal power series, in: Z. Ésik, Z. Fülöp (Eds.), Proc. 11th Internat. Conf. Automata and Formal Languages, Institute of Informatics, University of Szeged, 2005, pp. 164-177. |
| [19] | W. Kuich, On skew formal power series, in: S. Bozapalidis, A. Kalampakas, G. Rahonis (Eds.), Proc. Conf. Algebraic Informatics, Thessaloniki, 2005, pp. 7-30.; W. Kuich, On skew formal power series, in: S. Bozapalidis, A. Kalampakas, G. Rahonis (Eds.), Proc. Conf. Algebraic Informatics, Thessaloniki, 2005, pp. 7-30. |
| [20] | Kuich, W.; Salomaa, A., Semirings, automata, languages, EATCS Monographs in Theoretical Computer Science, vol. 5 (1986), Springer: Springer Berlin · Zbl 0582.68002 |
| [21] | Li, Y.; Pedrycz, W., Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids, Fuzzy Sets and Systems, 156, 68-92 (2005) · Zbl 1083.68059 |
| [22] | Mordeson, J.; Malik, D., Fuzzy Automata and Languages: Theory and Applications (2002), Chapman & Hall: Chapman & Hall CRC Boca Raton, London, New York, Washington, DC · Zbl 1046.68068 |
| [23] | Rahonis, G., Infinite fuzzy computations, Fuzzy Sets and Systems, 153, 275-288 (2005) · Zbl 1138.68433 |
| [24] | Ray, A.; Chatterjee, B.; Majumdar, A., A formal power series approach to the construction of minimal fuzzy automata, Inform. Sci., 55, 1-5, 189-207 (1991) · Zbl 0717.68059 |
| [25] | Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025 |
| [26] | Santos, E., Regular Fuzzy Expressions, (Fuzzy Automata and Decision Processes (1977), North-Holland: North-Holland New York), 169-175 |
| [27] | Schützenberger, M., On the definition of a family of automata, Inf. Control, 4, 245-270 (1961) · Zbl 0104.00702 |
| [28] | Sheng, L.; Li, Y., Regular grammars with truth values in lattice-monoid and their languages, Soft Comput., 10, 79-86 (2006) · Zbl 1084.68066 |
| [29] | Wechler, W., The Concept of Fuzziness in Automata and Language Theory (1978), Akademie Verlag: Akademie Verlag Berlin · Zbl 0401.94048 |
| [30] | Ying, M., A formal model of computing with words, IEEE Trans. Fuzzy Systems, 10, 640-652 (2002) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
