×
Goldstine, Jonathan; Price, John K.; Wotschke, Detlef

A pushdown automaton or a context-free grammar - which is more economical? (English) Zbl 0486.68082

Theor. Comput. Sci. 18, 33-40 (1982).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0486.68082

Cited in 11 Documents

MSC:

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity

Keywords:

real-time deterministic pushdown automaton; context-free languages

Citations:

Zbl 0381.68054
Cite Review PDF
Full Text: DOI

References:

[1] Aho, A. V.; Ullman, J. D., The Theory of Parsing, Translation, and Compiling, Vol. 1 (1972), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0264.68032
[2] Geller, M. M.; Hunt, H. B.; Szymanski, T. G.; Ullman, J. D., Economy of description by parsers, DPDAs and PDAs, Theoret. Comput. Sci., 4, 143-153 (1977) · Zbl 0357.68086
[3] Ginsburg, S., The Mathematical Theory of Context-Free Languages (1966), McGraw-Hill: McGraw-Hill New York · Zbl 0184.28401
[4] Ginsburg, S.; Lynch, N., Size complexity in context-free grammar forms, J. ACM, 23, 582-598 (1976) · Zbl 0333.68057
[5] Ginsburg, S.; Spanier, E. H., Finite-turn pushdown automata, SIAM J. Control, 4, 423-434 (1966) · Zbl 0147.25302
[6] Gruska, J., Descriptional complexity (of languages), a short survey, (Proc. Conference on Mathematical Foundations of Computer Science, Gdansk, September 1976. Proc. Conference on Mathematical Foundations of Computer Science, Gdansk, September 1976, Lecture Notes in Computer Science, 45 (1976), Springer: Springer Berlin), 65-80 · Zbl 0338.68040
[7] Hopcroft, J. E.; Ullman, J. D., Formal Languages and their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[8] Meyer, A. R.; Fischer, M. J., Economy of description by automata, grammars, and formal systems, Proc. 12th Symposium on Switching and Automata Theory, 188-191 (1971)
[9] Ogden, W., A helpful result for proving inherent ambiguity, Math. Systems Theory, 2, 191-194 (1968) · Zbl 0175.27802
[10] Pirická, A., Complexity and normal forms of context-free languages, (Proc. Conference on Mathematical Foundations of Computer Science, June 1974. Proc. Conference on Mathematical Foundations of Computer Science, June 1974, Lecture Notes in Computer Science, 28 (1974), Springer: Springer Berlin), 292-297 · Zbl 0312.68038
[11] Pirická-Kelemenová, A., Greibach normal form complexity, (Proc. Conference on Mathematical Foundations of Computer Science, September 1975. Proc. Conference on Mathematical Foundations of Computer Science, September 1975, Lecture Notes in Computer Science, 32 (1975), Springer: Springer Berlin), 344-350 · Zbl 0318.68049
[12] Schmidt, E.; Szymanski, T., Succinctness of descriptions of unambiguous context-free languages, SIAM J. Comput., 6, 547-553 (1977) · Zbl 0357.68088
[13] Valiant, L. G., A note on the succinctness of descriptions of deterministic languages, Information and Control, 32, 139-145 (1976) · Zbl 0338.68059
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.