A note on the recognition of one counter languages

 Access to full text

 Full (PDF)

1. [1] D. H. YOUNGER, Recognition and parsing of context-free languages in time n3, Information and Control, (1967), 10, 189-208. Zbl0149.24803
2. [2] P. M. LEWIS, R. E. STEARNS and J. HARTMANIS, Memory bounds for recognition of context-free and context-sensitive languages, IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann. Arbor, Michigan, 1965, 191-202. Zbl0272.68054
3. [3] S. A. GREIBACH, The Hardest Context-free Language, SIAM J. Computing, (1973), 2, 304-310. Zbl0278.68073
4. [4] T. KASAMI, A note on computing time for recognition of languages generated by linear grammars, Information and Control, (1967), 10, 209-214. Zbl0163.01002
5. [5] A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, Time and tape complexity of pushdown automaton languages, Information and Control, (1968), 13, 186-206. Zbl0257.68065
6. [6] P. C. FISCHER, A. R. MEYER and A. L. ROSENBERG, Counter machines and counter languages, Math Systems Theory, (1968), 2. 265-283. Zbl0165.32002
7. [7] S. A. GREIBACH, Erasable context-free languagse, to appear. Zbl0317.68059
8. [8] S. GINSBURG, and G. F. ROSE, The equivalence of stack counter acceptors and quasi-realtime acceptors, J. Computer System Science, (1974), 8, 243-269. Zbl0275.68017
9. [9] S. GINSBURG, and S. GREIBACH, Deterministic context-free languages, Information and Control, (1966), 9, 620-648. Zbl0145.00802
10. [10] O. H. IBARRA, On two-way multihead automata, Computer System Sciences, (1973), 7, 28-36. Zbl0256.68028
11. [11] S. GREIBACH, Remarks on the complexity of nondeterministic counter languages, to appear. Zbl0332.68039
12. [12] S. GINSBURG, The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York, 1966. Zbl0184.28401

1. I. H. Sudborough, Some remarks on multihead automata
2. S. A. Greibach, A note on NSPACE (${log}_{2}n$) and substitution