Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines

M. Krause; Ch. Meinel; St. Waack

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1992)

  • Volume: 26, Issue: 4, page 345-362
  • ISSN: 0988-3754

How to cite

top

Krause, M., Meinel, Ch., and Waack, St.. "Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 26.4 (1992): 345-362. <http://eudml.org/doc/92422>.

@article{Krause1992,
author = {Krause, M., Meinel, Ch., Waack, St.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {logarithmic space-bounded nondeterministic Turing machines},
language = {eng},
number = {4},
pages = {345-362},
publisher = {EDP-Sciences},
title = {Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines},
url = {http://eudml.org/doc/92422},
volume = {26},
year = {1992},
}

TY - JOUR
AU - Krause, M.
AU - Meinel, Ch.
AU - Waack, St.
TI - Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1992
PB - EDP-Sciences
VL - 26
IS - 4
SP - 345
EP - 362
LA - eng
KW - logarithmic space-bounded nondeterministic Turing machines
UR - http://eudml.org/doc/92422
ER -

References

top
  1. [AM86] N. ALON and W. MAASS, Meanders, Ramsey Theory and Lower Bounds, Proc. 27th I.E.E.E. FOCS 410-417, 1986. 
  2. [Im87] N. IMMERMAN, Nondeterministic Space is Closed Under Complement, Techn. Report 552, Yale Univ., 1987. MR961049
  3. [KL80] R. M. KARP and R. J. LIPTON, Some Connections Between Nonuniform and Uniform Complexity Classes, Proc. 12th A.C.M. Symp. on Theory of Computing, 302-309 1980. 
  4. [KMW91] M. KRAUSE, Ch. MEINEL and S. WAACK, Separating the Eraser Turing Machine Classes Le, NLe, co-NLe and Pe, Theoret. Comput. Sci., 1991, 86, pp. 267-275. Zbl0749.68036MR1122791
  5. [Kr91] M. KRAUSE, Lower Bounds for Depth-Restricted Branching programs, Inform. and Comput., 1991, 91, pp. 1-14. Zbl0800.68495MR1097261
  6. [KW91] M. KRAUSE and S. WAACK, On Oblivious Branching Programs of Linear Length, Inform. and Comput., 1991, 94, pp. 232-249. Zbl0727.68038MR1127534
  7. [Me86] Ch. MEINEL, p-Projection Reducibility and the Complexity Classes L (Nonuniform) and NL (Nonuniform), Proc. 12th MFCS, Bratislava, LNCS 233, pp.527-535; revised and extended version in EIK, 1987, 23, 10/11, pp. 545-558. Zbl0611.03021MR935269
  8. [Me88] Ch. MEINEL, The Power of Polynomial Size Ω-Branching Programs, Proc. STAC'88, Bordeaux, L.N.C.S. n° 294, pp. 81-90. Zbl0644.68074MR935789
  9. [Ru81] W. Ruzzo, On Uniform Circuit Complexity, J. Comput. System Sci., 1981, 22, (3), pp. 236-283. Zbl0462.68013MR633540
  10. [SV81] S. SKYUM and L. VALIANT, A Complexity Theory Based on Boolean Algebra, Proc. 22th LE.E.E. F.O.C.S., 1981, pp. 244-253. 
  11. [Sz87] R. SZELEPCSENYI, The Method of Forcing for Nondeterministic Automata, Bulletin of the E.A.T.C.S., 1987, 33, pp. 96-99. Zbl0664.68082
  12. [We87] I. WEGENER, The Complexity of Boolean Functions, Teubner, Stuttgart, 1987. Zbl0623.94018MR905473

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.