Pumping Lemma in context-free grammar theory based on complete residuated lattice-valued logic. (English) Zbl 1187.68305
Summary: Residuated lattices are important algebras and have close links with various important algebras. Automata theory based on complete residuated lattice-valued logic, called \(\mathcal L\)-valued automata, has been established by the second author in 2001 and 2002. As a continuation of automata theory based on complete residuated lattice-valued logic, in this paper, we mainly deal with the problem concerning pumping lemma in \(\mathcal L\)-valued context-free languages (\(\mathcal L\)-CFLs). As a generalization of the notion in the theory of formal grammars, the definition of \(\mathcal L\)-valued context-free grammars (\(\mathcal L\)-CFGs) is introduced. We also discuss a special case of \(\mathcal L\)-CFGs, \(\mathcal L\)-right (or left)-linear grammars, and show the equivalence between \(\mathcal L\)-linear grammars and \(\mathcal L\)-regular grammars. This result shows that we generalize the pumping lemma in \(\mathcal L\)-valued regular languages (\(\mathcal L\)-RLs) more recently established by the second author.
References:
| [1] | Dubois, D.; Prade, H., Fuzzy Sets and Systems: Theory and Applications (1980), Academic Press: Academic Press New York · Zbl 0444.94049 |
| [2] | DePalma, G. F.; Yau, S. S., Fractional fuzzy grammars with application to patten recognition, (Zadeh, L. A.; Fu, K. S.; Tanaka, K.; Shimura, M., Fuzzy Sets and Their Applications to Cognitive and Decision Processes (1975), Academic Press: Academic Press New York), 329-351 · Zbl 0329.68071 |
| [3] | Giles, C.; Omlin, C.; Thorber, K. K., Equivalence in knowledge representation: automata, recurrent neural networks, and dynamical fuzzy systems, Proc. IEEE, 87, 1623-1640 (1999) |
| [4] | Hikmet, S., Fuzzy command grammars for intelligent interface design, IEEE Trans. Systems Man Cybernet., 22, 1124-1131 (1992) |
| [5] | Hopcroft, J. E.; Motwani, R.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (2001), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0980.68066 |
| [6] | Kin, H. H.; Mizumoto, M.; Toyoda, J.; Tanaka, K., L-fuzzy grammar, Inform. Sci., 8, 123-140 (1975) · Zbl 0304.68072 |
| [7] | Lee, E. T.; Zadeh, L. A., Note on fuzzy languages, Inform. Sci., 1, 421-434 (1969) |
| [8] | Malik, D. S.; Mordeson, J. N., On Fuzzy Regular languages, Inform. Sci., 88, 263-273 (1996) · Zbl 0880.68074 |
| [9] | Malik, D. S.; Mordeson, J. N., Fuzzy Discrete Structures (2000), Physica-Verlag: Physica-Verlag Heidelberg, New York · Zbl 0966.68098 |
| [10] | Mordeson, J. N.; Malik, D. S., Fuzzy Automata and Languages: Theory and Applications (2002), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton, London · Zbl 1046.68068 |
| [11] | Omlin, C.; Thorber, K. K.; Giles, C., Fuzzy finite state automata can be deterministically encoded into recurrent neural networks, IEEE Trans. Fuzzy Systems, 6, 76-89 (1998) |
| [12] | Pavelka, J., On fuzzy logic I, II, III, Zeitschr \(f\) math Logik und Grundlagen \(d\) Math, 25, 45-52 (1979), 119-134; 447-464 · Zbl 0435.03020 |
| [13] | Paz, A., Introduction to Probabilistic Automata (1971), Academic Press: Academic Press New York/London · Zbl 0234.94055 |
| [14] | Peter, L., An Introduction to Formal Languages and Automata (2001), Jones & Bartlett Publishers: Jones & Bartlett Publishers Boston |
| [15] | Qiu, D. W., Automata theory based on complete residuated lattice-valued logic(I), Sci. in China (Ser. F), 44, 6, 419-429 (2001) · Zbl 1125.68383 |
| [16] | Qiu, D. W., Automata theory based on complete residuated lattice-valued logic(II), Sci. in China (Ser. F), 45, 6, 442-452 (2002) · Zbl 1161.68549 |
| [17] | Qiu, D. W., Characterizations of fuzzy finite automata, Fuzzy Sets and Systems, 141, 391-414 (2004) · Zbl 1059.68069 |
| [18] | Qiu, D. W., Pumping lemma in automata theory based on complete residuated lattice-valued logic: a note, Fuzzy Sets and Systems, 157, 2128-2138 (2006) · Zbl 1121.03048 |
| [19] | Qiu, D. W., Supervisory control of fuzzy discrete event systems: a formal approach, IEEE Trans. Systems. Man and Cyber., 35, 1, 72-88 (2005) |
| [20] | Qiu, D. W., A note on Trilla’s CHC models, Artificial Intelligence, 171, 239-254 (2007) · Zbl 1168.06302 |
| [21] | Rescher, N., Many-Valued Logic (1969), McGraw-Hill: McGraw-Hill New York · Zbl 0248.02023 |
| [22] | Rosser, J. B.; Turquette, A. R., Many-Valued Logics (1952), North-Holland: North-Holland Amsterdam · Zbl 0063.06587 |
| [23] | Steimann, F.; Adlassning, K. P., Clinical monitoring with fuzzy automata, Fuzzy Sets and Systems, 61, 37-42 (1994) |
| [24] | Xing, H. Y.; Qiu, D. W.; Liu, F. C.; Fan, Z. J., Equivalence in automata theory based on complete residuated lattice-valued logic, Fuzzy Sets and Systems, 158, 1407-1422 (2007) · Zbl 1152.68463 |
| [25] | Ying, M. S., Fuzzifying topology based on complete residuated lattice valued logic(I), Fuzzy Sets and Systems, 56, 337-373 (1993) · Zbl 0787.54010 |
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.
