zbMATH — the first resource for mathematics

A lower bound for the nondeterministic space complexity of context-free recognition. (English) Zbl 0780.68081
Summary: We prove a \(\log n\) lower bound on the nondeterministic space complexity of every nonregular deterministic context-free language.

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Alt, H., Lower bounds on space complexity for context-free recognition, Acta inform., 12, 33-61, (1979) · Zbl 0389.68043
[2] Alt, H.; Mehlhorn, K., Lower bounds for the space complexity of context-free recognition, (), 338-354 · Zbl 0368.68069
[3] V. Geffert, Tally versions of Savitch’s and Immermann-Szelepcsényi theorems for sublogarithmic space, SIAM J. Comput., to appear.
[4] Hopcroft, J.E.; Ullman, J.D., Formal languages and their relation to automata, (1969), Addison-Wesley Reading, MA · Zbl 0196.01701
[5] Immermann, N., Nondeterministic space is closed under complementation, SIAM J. comput., 17, 935-938, (1988) · Zbl 0668.68056
[6] Lewis, P.M.; Hartmanis, J.; Stearns, R.E., Memory bounds for the recognition of context-free and context-sensitive languages, IEEE conf. record on switching circuit theory and logical design, 179-202, (1965)
[7] Stearns, R.E., A regularity test for pushdown-machines, Inform. and control, 323-340, (1967) · Zbl 0155.01901
[8] Szelepcsényi, R., The method of forced enumeration for nondeterministic automata, Acta inform., 26, 279-284, (1988) · Zbl 0638.68046
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.