Some modifications of auxiliary pushdown automata
G. Buntrock; F. Drewes; C. Lautemann; T. Mossakowski
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1991)
- Volume: 25, Issue: 6, page 545-556
- ISSN: 0988-3754
Access Full Article
top
How to cite
topBuntrock, G., et al. "Some modifications of auxiliary pushdown automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 25.6 (1991): 545-556. <http://eudml.org/doc/92404>.
@article{Buntrock1991,
author = {Buntrock, G., Drewes, F., Lautemann, C., Mossakowski, T.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {logarithmic space; auxiliary pushdown automata; LBA problem},
language = {eng},
number = {6},
pages = {545-556},
publisher = {EDP-Sciences},
title = {Some modifications of auxiliary pushdown automata},
url = {http://eudml.org/doc/92404},
volume = {25},
year = {1991},
}
TY - JOUR
AU - Buntrock, G.
AU - Drewes, F.
AU - Lautemann, C.
AU - Mossakowski, T.
TI - Some modifications of auxiliary pushdown automata
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1991
PB - EDP-Sciences
VL - 25
IS - 6
SP - 545
EP - 556
LA - eng
KW - logarithmic space; auxiliary pushdown automata; LBA problem
UR - http://eudml.org/doc/92404
ER -
References
top- 1. F.-J. BRANDENBURG, On One-Way Auxiliary Pushdown Automata, Proc. 3rd GI Conf., Lecture Notes in Comput. Sci., 1977, 48, pp. 132-144. Zbl0359.68055MR483712
- 2. G. BUNTROCK, On the Robustness of the Polynomial Time Hierarchy, Technical report, No. 87-11, Technische Universität Berlin, 1987.
- 3. M. P. CHYTIL, Analysis of the Non-Context-Free Component of Formal Languages, Lecture Notes in Comput. Sci., 1976, 45, pp. 230-236. Zbl0339.68043
- 4. S. A. COOK, The Complexity of Theorem Proving Procedures. 3rd STOC, 1971, pp. 151-158. Zbl0253.68020
- 5. S. A. COOK, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, J. Assoc. Comput. Mach., 1971, 18, pp. 4-18. Zbl0222.02035MR292605
- 6. J. HARTMANIS and H. B. HUNT III, The LBA Problem and lts Importance in the Theory of Computing, S.I.A.M.-A.M.S. Proc., 1974, 7, pp. 1-26. Zbl0301.68056
- 7. J. HARTMANIS, N. IMMERMAN and S. MAHANEY, One-Way Log-Tape Reductions, 19th F.O.C.S., 1978, pp. 65-71. MR539830
- 8. J. HARTMANIS and S. MAHANEY, Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata, S.I.A.M.J. Comput., 1981, 10, pp. 383-390. Zbl0471.68059MR615226
- 9. J. E. HOPCROFT and D. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. Zbl0426.68001MR645539
- 10. N. IMMERMAN, Nondeterministic Space is Closed Under Complement, S.I.A.M. J. Comput., 1988, 17, pp. 935-938. Zbl0668.68056MR961049
- 11. S.-Y. KURODA, Classes of Languages and Linear-Bounded Automata, Inform. and Contr., 1964, 7, pp. 207-223. Zbl0199.04002MR169724
- 12. C. LAUTEMANN, One Pushdown and a Small Tape. In K. W. WAGNER Ed., Dirk Siefkes zum 50. Geburtstag, Technische Universität Berlin/Universität Augsburg, 1988, pp. 42-47.
- 13. I. NIEPEL, Logarithmisch platzbeschränkte Komplexitätsklassen: Charakterisierungen und offene Fragen, Diplomarbeit, Universität Hamburg, 1987.
- 14. I. H. SUDBOROUGH, On the Tape Complexity of Deterministic Context-Free Languages, J. Assoc. Comput. Mach., 1987, 25, pp. 405-414. Zbl0379.68054MR498563
- 15. R. SZELEPCSÉNYI, The Method of Forced Enumeration for Nondeterministic Automata, Acta Inform., 1988, 26, pp. 279-284. Zbl0638.68046MR975334
- 16. K. W. WAGNER and G. WECHSUNG, Computational Complexity, Reidel Verlag, Dordrecht, and V.E.B. Deutscher Verlag der Wissenschaften, Berlin, 1986. Zbl0584.68061MR831432
NotesEmbed ?
topYou 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.