Geodesic
A note on NSPACE (log 2 n) and substitution
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977) no. 2, pp. 127-132.

Voir la notice de l'article provenant de la source Numdam

@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},
     pages = {127--132},
     publisher = {Centrale des revues, Dunod-Gauthier-Villars},
     address = {Montreuil},
     volume = {11},
     number = {2},
     year = {1977},
     mrnumber = {455542},
     zbl = {0359.68090},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ITA_1977__11_2_127_0/}
}
TY  - JOUR
AU  - Greibach, S. A.
TI  - A note on NSPACE ($\log _2 n$) and substitution
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1977
SP  - 127
EP  - 132
VL  - 11
IS  - 2
PB  - Centrale des revues, Dunod-Gauthier-Villars
PP  - Montreuil
UR  - http://geodesic.mathdoc.fr/item/ITA_1977__11_2_127_0/
LA  - en
ID  - ITA_1977__11_2_127_0
ER  - 
%0 Journal Article
%A Greibach, S. A.
%T A note on NSPACE ($\log _2 n$) and substitution
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1977
%P 127-132
%V 11
%N 2
%I Centrale des revues, Dunod-Gauthier-Villars
%C Montreuil
%U http://geodesic.mathdoc.fr/item/ITA_1977__11_2_127_0/
%G en
%F 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) no. 2, pp. 127-132. http://geodesic.mathdoc.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. | Zbl | MR

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

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

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. | mathdoc-id | MR | EuDML

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

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

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

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. | Zbl | MR

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. | Zbl | MR