The complexity of the membership problem for some extensions of context-free languagestFootnote†

†This work is supported in part by NSF Grant No. GJ-43228. Some of these results have appeared in conference proceedings, see [41] and [42].

References

• Rosenkrantz , D. J. 1968 . Programmed Grammars and Classes of Formal Languages . J. ACM , 16 : 107 – 131 .
   Google Scholar
• Ginsburg , S. , Greibach , S. A. and Harrison , M. A. 1967 . One-Way Stack Automata . J. ACM , 14 : 389 – 418 .
   Web of Science ®Google Scholar
• Cook , S. A. 1971 . The Complexity of Theorem Proving Procedures . in Proceedings of ThirdAnnual ACM Symposium on Theory of Computing , 14 : 151 – 158 .
   Google Scholar
• Karp , R. M. 1972 . “ Reducibility Among Combinatorial Problems ” . In in Complexity of Computer Computations , Edited by: Miller , R. E. and Thatcher , J. N. 85 – 104 . N.Y : Plenum Press .
   Google Scholar
• Hartmanis , J. and Hunt I I I , H. B. May 1973 . The LB A Problem and its Importance in the Theory of Computing , May , 73 – 171 . Ithaca, New York : Department of Computer Science, Cornell University . Technical Report 14850
   Google Scholar
• Aho , A. V. , Hopcroft , J. E. and Ullman , J. D. 1974 . The Design and Analysis of ComputerAlgorithms , Addison-Wesley Publishing Co . Reading, Mass
   Google Scholar
• Shamir , E. and Beeri , C. 1974 . “ Checking Stacks and Context-Free Programmed Grammars Accept P-complete Languages ” . In in Automata, Languages and Programming , Vol. 14 , 27 – 33 . New York : Springer-Verlag Publishing Co . of Lecture Notes in Computer Science Series
   Google Scholar
• Van Leeuwen , J. 1975 . The Membership Question for ETOL-Languages is Polynomially Complete . Info. Processing Letters , 3 : 138 – 143 .
   Google Scholar
• Greibach , S. A. 1969 . Checking Automata and One-Way Stack Languages . J. of Computer and System Sciences , 3 : 196 – 217 .
   Google Scholar
• Herman , G. T. and Rozenberg , G. 1975 . Developmental Systems and Languages , Amsterdam : North-Holland Publishing Co .
   Google Scholar
• Jones , N. D. 1975 . Space-Bounded Reducibility among Combinatorial Problems . J. of Computer and System Sciences , 11 : 68 – 85 .
   Google Scholar
• Meyer , A. R. and Stockmeyer , L. J. 1973 . Word Problems Requiring Exponential Time . Proceedings of Fifth Annual ACM Symposium on Theory of Computing , 11 : 1 – 9 .
   Google Scholar
• Lewis , P.M. , Stearns , R.E. and Hartmans , J. Memory bounds for the recongnition of context-free and context-sensitive languages . Proceedings of the sixth annual IEEE Symposiun on Switching circuit theory and logical design . pp. 199 – 212 .
   Google Scholar
• Valiant , L. 1975 . General Context-Free Recognition in Less Than Cubic Time . J. Computer and System Sciences , 10 : 308 – 315 .
   Google Scholar
• Greibach , S. A. 1973 . The Hardest Context-Free Language . SI AM J. on Computing , 2 : 304 – 310 .
   Google Scholar
• Van Leeuwen , J. 1975 . The Tape Complexity of Context-Independent Developmental Languages . J. of Computer and System Sciences , 11 : 203 – 211 .
   Google Scholar
• Ginsburg , S. and Spanier , E. H. 1971 . AFL with the Semilinear Property . J. of Computer and System Sciences , 5 : 365 – 396 .
   Google Scholar
• Ibarra , O. H. 1970 . Simple Matrix Languages . Info. and Control , 17 : 359 – 394 .
   Google Scholar
• Khabbaz , N. A. 1974 . A Geometric Hierarchy of Languages . J. of Computer System Sciences , 8 : 142 – 157 .
   Google Scholar
• Kasai , T. 1970 . An Hierarchy Between Context-Free and Context-Sensitive Languages . J.of Computer and System Sciences , 4 : 492 – 508 .
   Google Scholar
• Cremers , A. B. and Mayer , O. 1974 . On Vector Languages . J. of Computer and System Sciences , 8 : 142 – 157 .
   Google Scholar
• Aho , A. V. and Ullman , J. D. 1972 . The Theory of Parsing, Translation, and Compiling Vol I , Englewood Cliffs, New Jersey : Prentice-Hall Publishing Co .
   Google Scholar
• Ginsburg , S. 1966 . The Mathematical Theory of Context-FreeLanguages , New York : McGraw-Hill Publishing Co .
   Google Scholar
• Ginsburg , S. and Spanier , E. H. 1968 . Control Sets on Grammars . Mathematical SystemsTheory , 2 : 159 – 177 .
   Google Scholar
• Salomaa , A. 1973 . Formal Languages , New York : Academic Press Inc .
   Google Scholar
• Hopcroft , J. E. and Ullman , J. D. 1969 . Formal Languages and Their Relation to Automata , Addison-Wesley Publishing Co . Reading, Mass
   Google Scholar
• Hartmanis , J. and Hopcroft , J. E. 1971 . An Overview of the Theory of Computational Complexity . J. ACM , 18 : 444 – 475 .
   Google Scholar
• Sudborough , I. H. 1976 . On the Tape Complexity of Deterministic Context-Free Languages . Some of these results are in Proceedings of Eighth Annual ACM Symposium on Theory of Computing , 18 : 141 – 148 . J.ACM to appear
   Google Scholar
• Ginsburg , S. and Greibach , S. A. 1966 . Deterministic Context-Free Languages . Inf. and Control , 9 : 620 – 648 .
   Google Scholar
• Cook , S. A. 1971 . Characterizations of Pushdown Machines in Terms of Time-Bounded Computers . J. ACM , 18 : 4 – 18 .
   Web of Science ®Google Scholar
• Ginsburg , S. and Spanier , E. H. 1966 . Finite-Turn Pushdown Automata . SI AM J. on Control , 4 : 429 – 453 .
   Google Scholar
• Sudborough , I. H. 1975 . A Note on Tape-Bounded Complexity Classes and Linear Context-FreeLanguages . J. ACM , 22 : 499 – 500 .
   Google Scholar
• Ibarra , O. H. 1973 . On Two-Way Multihead Automata . J. of Computer and System Sciences , 1 : 28 – 36 .
   Google Scholar
• Harrison , M. A. and Ibarra , O. H. 1968 . Multitape and Multihead Pushdown Automata . Inf. andControl , 13 : 433 – 470 .
   Google Scholar
• I. H. Sudborough Some Remarks on Multihead Automata to appear
   Google Scholar
• Rozenberg , G. and Salomaa , A. 1974 . New York : Springer-Veriag Publishing Co . in Lecture Notes in Computer Science
   Google Scholar
• Abraham , S. 1965 . Some Questions of Phrase Structure Grammars . Computational Linguistics , 4 : 61 – 70 .
   Google Scholar
• Salomaa , A. 1970 . Periodically Time-Variant Context-Free Grammars . Info. and Control , 17 : 294 – 311 .
   Google Scholar
• Salomaa , A. 1972 . Matrix Grammars with a Leftmost Restriction . Info. and Control , 20 : 143 – 149 .
   Google Scholar
• Cremers , A. B. and Mayer , O. 1973 . On Matrix Languages . Info. and Control , 23 : 86 – 96 .
   Google Scholar
• Arora , A. K. and Sudborough , I. H. 1976 . “ On Languages Log-Tape Reducible to Context-Free Languages ” . In Conf. on Info. Sciences and Systems , 27 – 32 . Johns Hopkins University .
   Google Scholar
• Sudborough , I. H. 1977 . “ The Time and Tape Complexity of Developmental Languages ” . In Fourth International Colloquium on Automata, Languages, and Programming Turku, , Finland
   Google Scholar