×

On equivalence of grammars through transformation trees. (English) Zbl 0409.68041


MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bar-Hillel, Y.; Perles, M.; Shamir, E., On formal properties of simple phrase structure grammars, Z. Phonetik Sprachwiss. Kommunikat., 14, 143-172 (1961) · Zbl 0106.34501
[2] Courcelle, B., Une forme canonique pour les grammaires simples déterministes, RAIRO, R-1, 19-36 (1974) · Zbl 0285.68033
[3] Friedman, E. P., The inclusion problem for simple languages, Theoret. Comput. Sci., 1, 297-316 (1976) · Zbl 0349.68032
[4] Geller, M. M.; Harrison, M. A.; Havel, I. M., Normal forms of deterministic grammars, Discrete Math., 16, 313-321 (1976) · Zbl 0358.68108
[5] Ginsburg, S.; Greibach, S. A., Deterministic context free languages, Information and Control, 9, 620-648 (1966) · Zbl 0145.00802
[6] Greibach, S. A., A new normal-form theorem for context-free phrase structure grammars, J. ACM, 12, 42-52 (1965) · Zbl 0135.18404
[7] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[8] Harrison, M. A.; Havel, I. M., Real-time strict deterministic languages, SIAM J. Comput., 1, 333-349 (1972) · Zbl 0267.68034
[9] Harrison, M. A.; Havel, I. M., Strict deterministic grammars, J. Comput. System Sci., 7, 237-277 (1973) · Zbl 0261.68036
[10] Harrison, M. A.; Havel, I. M., On the parsing of deterministic languages, J. ACM, 21, 525-548 (1974) · Zbl 0296.68084
[11] Hopcroft, J. E., On the equivalence and containment problems for context-free languages, Math. Systems Theory, 3, 119-124 (1969) · Zbl 0179.02203
[12] Hopcroft, J. E.; Ullman, J. D., Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[13] Korenjak, A. J.; Hopcroft, J. E., Simple deterministic languages, Conference Record of IEEE 7th Annual Symposium on Switching and Automata Theory, 36-46 (1966), Berkeley, California · Zbl 0313.68061
[14] Linna, M., Two decidability results for deterministic pushdown automata, J. Comput. System Sci., 18, 92-107 (1979) · Zbl 0399.03023
[15] Olshansky, T.; Pnueli, A., A direct algorithm for checking equivalence of LL(k) grammars, Theoret. Comput. Sci., 4, 321-349 (1977) · Zbl 0358.68118
[16] J. Pittl, On two subclasses of real-time grammars, unpublished manuscript, Charles University, Prague.; J. Pittl, On two subclasses of real-time grammars, unpublished manuscript, Charles University, Prague.
[17] Rosenkrantz, D. J.; Stearns, R. E., Properties of deterministic top-down grammars, Information and Control, 17, 226-256 (1970) · Zbl 0209.02703
[18] Salomaa, A., Comparative decision problems between sequential and parallel rewriting, First International Symposium on Uniformly Structured Automata and Logic. First International Symposium on Uniformly Structured Automata and Logic, IEEE 75 CH 10502-OC, 62-66 (1975)
[19] Semenov, A. L., Algorithmic problems for power series and context-free grammars, Dokl. Akad. Nauk SSSR, 212, 50-52 (1973), (in Russian) · Zbl 0322.68052
[20] Taniguchi, K.; Kasami, T., A result on the equivalence problem for deterministic pushdown automata, J. Comput. System Sci., 13, 38-50 (1976) · Zbl 0337.68032
[21] Valiant, L. G., Decision procedures for families of deterministic pushdown automata (1973), University of Warwick, Computer Centre Report 7
[22] Valiant, L. G., The equivalence problem for deterministic finite-turn pushdown automata, Information and Control, 25, 123-133 (1974) · Zbl 0285.68025
[23] Valiant, L. G.; Paterson, M. S., Deterministic one-counter automata, J. Comput. System Sci., 10, 340-350 (1975) · Zbl 0307.68038
[24] Wood, D., Some remarks on the KH algorithm for \(s\)-grammars, BIT, 13, 476-489 (1973) · Zbl 0301.68080
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.