EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 25 / No 6 (1991) RAIRO-Theor. Inf. Appl., 25 6 (1991) 545-556 References
Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 25, Number 6, 1991
Page(s) 545 - 556
DOI https://doi.org/10.1051/ita/1991250605451
Published online 01 February 2017
  1. 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] [Google Scholar]
  2. 2. G. BUNTROCK, On the Robustness of the Polynomial Time Hierarchy, Technical report, No. 87-11, Technische Universität Berlin, 1987. [Google Scholar]
  3. 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] [Google Scholar]
  4. 4. S. A. COOK, The Complexity of Theorem Proving Procedures. 3rd STOC, 1971, pp. 151-158. [Zbl: 0253.68020] [Google Scholar]
  5. 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] [Google Scholar]
  6. 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] [Google Scholar]
  7. 7. J. HARTMANIS, N. IMMERMAN and S. MAHANEY, One-Way Log-Tape Reductions, 19th F.O.C.S., 1978, pp. 65-71. [MR: 539830] [Google Scholar]
  8. 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] [Google Scholar]
  9. 9. J. E. HOPCROFT and D. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. [MR: 645539] [Zbl: 0426.68001] [Google Scholar]
  10. 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] [Google Scholar]
  11. 11. S.-Y. KURODA, Classes of Languages and Linear-Bounded Automata, Inform. and Contr., 1964, 7, pp. 207-223. [MR: 169724] [Zbl: 0199.04002] [Google Scholar]
  12. 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. [Google Scholar]
  13. 13. I. NIEPEL, Logarithmisch platzbeschränkte Komplexitätsklassen: Charakterisierungen und offene Fragen, Diplomarbeit, Universität Hamburg, 1987. [Google Scholar]
  14. 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] [Google Scholar]
  15. 15. R. SZELEPCSÉNYI, The Method of Forced Enumeration for Nondeterministic Automata, Acta Inform., 1988, 26, pp. 279-284. [MR: 975334] [Zbl: 0638.68046] [Google Scholar]
  16. 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] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.