Recherche et téléchargement d’archives de revues mathématiques numérisées

 
 
  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

Bibliographie

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 2014 | Crédit | Plan du site