Some modifications of auxiliary pushdown automata
Buntrock, G. ; Drewes, F. ; Lautemann, C. ; Mossakowski, T.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991), p. 545-556 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1991-01-01
@article{ITA_1991__25_6_545_0,
     author = {Buntrock, G. and Drewes, F. and Lautemann, C. and Mossakowski, T.},
     title = {Some modifications of auxiliary pushdown automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {25},
     year = {1991},
     pages = {545-556},
     mrnumber = {1145427},
     zbl = {0705.68051},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1991__25_6_545_0}
}

Buntrock, G.; Drewes, F.; Lautemann, C.; Mossakowski, T. Some modifications of auxiliary pushdown automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) pp. 545-556. http://gdmltest.u-ga.fr/item/ITA_1991__25_6_545_0/

1. F.-J. Brandenburg, On One-Way Auxiliary Pushdown Automata, Proc. 3rd GI Conf., Lecture Notes in Comput. Sci., 1977, 48, pp. 132-144. | MR 483712 | Zbl 0359.68055

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. | Zbl 0339.68043

4. S. A. Cook, The Complexity of Theorem Proving Procedures. 3rd STOC, 1971, pp. 151-158. | Zbl 0253.68020

5. S. A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, J. Assoc. Comput. Mach., 1971, 18, pp. 4-18. | MR 292605 | Zbl 0222.02035

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. | Zbl 0301.68056

7. J. Hartmanis, N. Immerman and S. Mahaney, One-Way Log-Tape Reductions, 19th F.O.C.S., 1978, pp. 65-71. | MR 539830

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. | MR 615226 | Zbl 0471.68059

9. J. E. Hopcroft and D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. | MR 645539 | Zbl 0426.68001

10. N. Immerman, Nondeterministic Space is Closed Under Complement, S.I.A.M. J. Comput., 1988, 17, pp. 935-938. | MR 961049 | Zbl 0668.68056

11. S.-Y. Kuroda, Classes of Languages and Linear-Bounded Automata, Inform. and Contr., 1964, 7, pp. 207-223. | MR 169724 | Zbl 0199.04002

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. | MR 498563 | Zbl 0379.68054

15. R. Szelepcsényi, The Method of Forced Enumeration for Nondeterministic Automata, Acta Inform., 1988, 26, pp. 279-284. | MR 975334 | Zbl 0638.68046

16. K. W. Wagner and G. Wechsung, Computational Complexity, Reidel Verlag, Dordrecht, and V.E.B. Deutscher Verlag der Wissenschaften, Berlin, 1986. | MR 831432 | Zbl 0584.68062 | Zbl 0584.68061