A note on the recognition of one counter languages
Greibach, S. A.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 9 (1975), p. 5-12 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1975-01-01
@article{ITA_1975__9_2_5_0,
     author = {Greibach, S. A.},
     title = {A note on the recognition of one counter languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {9},
     year = {1975},
     pages = {5-12},
     mrnumber = {391578},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1975__9_2_5_0}
}

Greibach, S. A. A note on the recognition of one counter languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 9 (1975) pp. 5-12. http://gdmltest.u-ga.fr/item/ITA_1975__9_2_5_0/

[1]D. H. Younger, Recognition and parsing of context-free languages in time n3, Information and Control, (1967), 10, 189-208. | Zbl 0149.24803

[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. | Zbl 0272.68054

[3] S. A. Greibach, The Hardest Context-free Language, SIAM J. Computing, (1973), 2, 304-310. | Zbl 0278.68073

[4] T. Kasami, A note on computing time for recognition of languages generated by linear grammars, Information and Control, (1967), 10, 209-214. | Zbl 0163.01002

[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. | Zbl 0257.68065

[6] P. C. Fischer, A. R. Meyer and A. L. Rosenberg, Counter machines and counter languages, Math Systems Theory, (1968), 2. 265-283. | Zbl 0165.32002

[7] S. A. Greibach, Erasable context-free languagse, to appear. | Zbl 0317.68059

[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. | Zbl 0275.68017

[9] S. Ginsburg, and S. Greibach, Deterministic context-free languages, Information and Control, (1966), 9, 620-648. | Zbl 0145.00802

[10] O. H. Ibarra, On two-way multihead automata, Computer System Sciences, (1973), 7, 28-36. | Zbl 0256.68028

[11] S. Greibach, Remarks on the complexity of nondeterministic counter languages, to appear. | Zbl 0332.68039

[12] S. Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York, 1966. | Zbl 0184.28401