A note on NSPACE (log 2 n) and substitution
Greibach, S. A.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977), p. 127-132 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1977-01-01
@article{ITA_1977__11_2_127_0,
     author = {Greibach, S. A.},
     title = {A note on NSPACE ($\log \_2 n$) and substitution},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {11},
     year = {1977},
     pages = {127-132},
     mrnumber = {455542},
     zbl = {0359.68090},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1977__11_2_127_0}
}

Greibach, S. A. A note on NSPACE ($\log _2 n$) and substitution. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977) pp. 127-132. http://gdmltest.u-ga.fr/item/ITA_1977__11_2_127_0/

1. R. V. Book, S. A. Greibach and B. Wegbreit, Time- and Tape-Bounded Turing Acceptors and AFLs, J. Computer System Sciences, 4, 1970, p. 606-621. | MR 267993 | Zbl 0206.28702

2. S. A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, J. Association Computing Machinery, 18, 1971, p. 4-18. | MR 292605 | Zbl 0222.02035

3. S. A. Greibach, Erasable Context-Free Languages, Information and Control, 29, 1975, p. 301-326. | MR 386358 | Zbl 0317.68059

4. S. A. Greibach, A Note on the Recognition of One Counter Languages, Revue Française d'Automatique, Informatique et Recherche Opérationnelle, R-2, 9, 1975, p. 5-12. | Numdam | MR 391578

5. S. A. Greibach, Remarks on the complexity of nondeterministic counter languages, Theoretical Computer Science, 1, 1976, 269-289. | MR 411257 | Zbl 0332.68039

6. O. H. Ibarra, A Note on Semilinear Sets and Bounded-reversal Multihead Pushdown Automata, Information Processing Letters, 3, 1974, 25-28. | MR 347142 | Zbl 0294.68019

7. O. H. Ibarra, On two-way multihead automata, J. Computer System Sciences, 7, 1973, p. 28-36. | MR 408317 | Zbl 0256.68028

8. O. H. Ibarra and C. E. Kim, A Useful Device for Showing the Solvability of Some Decision Problems, Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, Hershey, Pennsylvania, May, 1976, p. 135-140. | MR 451867 | Zbl 0365.68060

9. I. H. Sudborough, On Deterministic Context-Free Languages, Multihead Automata, and the Power of an Auxiliary Pushdown Store, Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, Hershey, Pennsylvania. May. 1976. p. 141-148. | MR 436674 | Zbl 0365.68077