A note on NSPACE ( log 2 n ) 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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.