×

A direct algorithm for checking equivalence of LL(k) grammars. (English) Zbl 0358.68118


MSC:

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

References:

[1] A.J. Korenjak and J.E. Hopcroft,Simple deterministic languages, IEEE Conf. Record of 7th Annual Symposium on Switching and Automata Theory, pp.36-46; A.J. Korenjak and J.E. Hopcroft,Simple deterministic languages, IEEE Conf. Record of 7th Annual Symposium on Switching and Automata Theory, pp.36-46 · Zbl 0313.68061
[2] Rosenkrantz, D. J.; Stearns, R. E., Properties of deterministic top down grammars, Information and Control, 17, 3, 226-256 (1979) · Zbl 0209.02703
[3] Friedman, E. P., Deterministic languages and monadic recursion schemes (1974), Center for Research in Computing Technology, Harvard University
[4] Valiant, L. G., Decision procedures for families of deterministic pushdown automata, (Ph.D. Thesis (1973), Department of Computer Science, University of Warwick: Department of Computer Science, University of Warwick Coventry, England) · Zbl 0566.94022
[5] Ashcroft, E.; Manna, A.; Pnueli, A., Decidable properties of monadic functional schemes, J. ACM, 20, 3, 489-499 (1973) · Zbl 0289.68036
[6] Gaiil, Z., Functional schemas with nested predicates, Information and Control, 27, 4, 349-368 (1975) · Zbl 0302.68097
[7] Engelfrict, J., Some program schemes and formal languages, (Lecture Notes in Computer Science, No. 20 (1974), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0288.68030
[8] Garland, S. J.; Luckham, D. C., Program schemes, recursion schemes and formal languages, J. Comp. System Sci., 7, 119-160 (1973) · Zbl 0369.68014
[9] Nivat, M., Sur l’interpretation des schemas de programme monadiques, (Symposium IRIA — Automata, Languages and Programming (1973), North-Holland: North-Holland Amsterdam) · Zbl 0279.68010
[10] Hopcroft, J. E.; Ullman, J. D., Formal Languages and their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[11] Aho, A. V.; Ullman, J. D., The Theory of Parsing, Translation and Compiling (1972), Prentice-Hall, Inc: Prentice-Hall, Inc Englewood Cliffs, NJ · Zbl 0264.68032
[12] T. Olshansky and A. Pnueli, A direct algorithm for checking equivalence of free \(Nk\); T. Olshansky and A. Pnueli, A direct algorithm for checking equivalence of free \(Nk\) · Zbl 0358.68118
[13] Courcelle, B.; Vuillemin, J., Completeness results for the equivalence of recursive schemes, J. Comput. System Sci., 12, 179-197 (1976) · Zbl 0342.68008
[14] Courcelle, B., Recursive schemes, algebraic trees and deterministic languages, 15th Annual Symposium SWAT, 52-62 (1974)
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.