| |
Table des matières de ce fascicule | Article précédent | Article suivant
Buntrock, G.; Drewes, F.; Lautemann, C.; Mossakowski, T.
Some modifications of auxiliary pushdown automata. Informatique théorique et applications, 25 no. 6 (1991), p. 545-556
Texte intégral djvu | pdf | Analyses MR 1145427 | Zbl 0705.68051
URL stable: http://www.numdam.org/item?id=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.68061
|
|
Copyright Cellule MathDoc 2013 | Crédit | Plan du site
|
