A note on NSPACE () and substitution

S. A. Greibach

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1977)

  • Volume: 11, Issue: 2, page 127-132
  • ISSN: 0988-3754

How to cite

top

Greibach, S. A.. "A note on NSPACE ($\log _2 n$) and substitution." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 11.2 (1977): 127-132. <http://eudml.org/doc/92046>.

@article{Greibach1977,
author = {Greibach, S. A.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
language = {eng},
number = {2},
pages = {127-132},
publisher = {EDP-Sciences},
title = {A note on NSPACE ($\log _2 n$) and substitution},
url = {http://eudml.org/doc/92046},
volume = {11},
year = {1977},
}

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
PB - EDP-Sciences
VL - 11
IS - 2
SP - 127
EP - 132
LA - eng
UR - http://eudml.org/doc/92046
ER -

References

top
  1. 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. Zbl0206.28702MR267993
  2. 2. S. A. COOK, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, J. Association Computing Machinery, 18, 1971, p. 4-18. Zbl0222.02035MR292605
  3. 3. S. A. GREIBACH, Erasable Context-Free Languages, Information and Control, 29, 1975, p. 301-326. Zbl0317.68059MR386358
  4. 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. MR391578
  5. 5. S. A. GREIBACH, Remarks on the complexity of nondeterministic counter languages, Theoretical Computer Science, 1, 1976, 269-289. Zbl0332.68039MR411257
  6. 6. O. H. IBARRA, A Note on Semilinear Sets and Bounded-reversal Multihead Pushdown Automata, Information Processing Letters, 3, 1974, 25-28. Zbl0294.68019MR347142
  7. 7. O. H. IBARRA, On two-way multihead automata, J. Computer System Sciences, 7, 1973, p. 28-36. Zbl0256.68028MR408317
  8. 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. Zbl0365.68060MR451867
  9. 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. Zbl0365.68077MR436674

NotesEmbed ?

top

You must be logged in to post comments.