@article{ITA_1977__11_2_127_0, author = {Greibach, S. A.}, title = {A note on {NSPACE} ($\log _2 n$) and substitution}, journal = {RAIRO. Informatique th\'eorique}, 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://www.numdam.org/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. Informatique théorique PY - 1977 SP - 127 EP - 132 VL - 11 IS - 2 PB - Centrale des revues, Dunod-Gauthier-Villars PP - Montreuil UR - http://www.numdam.org/item/ITA_1977__11_2_127_0/ LA - en ID - ITA_1977__11_2_127_0 ER -
Greibach, S. A. A note on NSPACE ($\log _2 n$) and substitution. RAIRO. Informatique théorique, Tome 11 (1977) no. 2, pp. 127-132. http://www.numdam.org/item/ITA_1977__11_2_127_0/
1. Time- and Tape-Bounded Turing Acceptors and AFLs, J. Computer System Sciences, 4, 1970, p. 606-621. | MR | Zbl
, and ,2. Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, J. Association Computing Machinery, 18, 1971, p. 4-18. | MR | Zbl
,3. Erasable Context-Free Languages, Information and Control, 29, 1975, p. 301-326. | MR | Zbl
,4. 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. | EuDML | Numdam | MR
,5. Remarks on the complexity of nondeterministic counter languages, Theoretical Computer Science, 1, 1976, 269-289. | MR | Zbl
,6. A Note on Semilinear Sets and Bounded-reversal Multihead Pushdown Automata, Information Processing Letters, 3, 1974, 25-28. | MR | Zbl
,7. On two-way multihead automata, J. Computer System Sciences, 7, 1973, p. 28-36. | MR | Zbl
,8. 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 | Zbl
and ,9. 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 | Zbl
,