A note on NSPACE () and substitution
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1977)
- Volume: 11, Issue: 2, page 127-132
- ISSN: 0988-3754
Access Full Article
topHow to cite
topReferences
top- 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. 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. S. A. GREIBACH, Erasable Context-Free Languages, Information and Control, 29, 1975, p. 301-326. Zbl0317.68059MR386358
- 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. S. A. GREIBACH, Remarks on the complexity of nondeterministic counter languages, Theoretical Computer Science, 1, 1976, 269-289. Zbl0332.68039MR411257
- 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. O. H. IBARRA, On two-way multihead automata, J. Computer System Sciences, 7, 1973, p. 28-36. Zbl0256.68028MR408317
- 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. 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