Abstract
In this article we study the time complexity of the recognition problem for some “moderate” extensions of context-free grammars or pushdown automata. It is well known that, for a given context-free grammar G, the recognition problem “x ∈ L(G)” can be decided in 0(|x|)3 steps by a suitable algorithm. How do extensions behave in this respect? In particular, do they admit recognition algorithms whose time is polynomially bounded by the length of the input?
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cook, S., The complexity of Theorem-Proving Procedures, Conf. Rec. 3rd ACM Symp. on Theory of Computing (1971), 151–158.
Karp, R., Reducibility Among Combinatorial Problems, in: Complexity of Computer Computations R. E. Miller and J. W. Thatcher, Editors, Plenum Press, N.Y. (1973), 85–104.
Stockmeyer, L. J., A. R. Meyer, Word Problems Requiring Exponential Time: Preliminary Report,Conf. Rec. 5th ACM Symp. on Theory of Computing (1973), 1–9.
Greibach, S., Checking Automata and One-Way Stack Languages, J. of Computer and System Sciences 3 (1969), 196–217.
Rosenkrantz, D. J., Programmed Grammars and Classes of Formal Languages, J. of the ACM (1969), 107–131.
Hunt, H. B. III, On the Time and Tape Complexity of Languages I Cornell University, Department of Computer Science, Technical Report No. 73–156, (1973).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1974 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shamir, E., Beeri, C. (1974). Checking Stacks and Context-Free Programmed Grammars Accept p-complete Languages. In: Loeckx, J. (eds) Automata, Languages and Programming. ICALP 1974. Lecture Notes in Computer Science, vol 14. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-21545-6_3
Download citation
DOI: https://doi.org/10.1007/978-3-662-21545-6_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-06841-9
Online ISBN: 978-3-662-21545-6
eBook Packages: Springer Book Archive