Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 26 (1992) no. 4, pp. 345-362.
@article{ITA_1992__26_4_345_0,
     author = {Krause, M. and Meinel, Ch. and Waack, St.},
     title = {Separating complexity classes related to certain input oblivious logarithmic space-bounded {Turing} machines},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {345--362},
     publisher = {EDP-Sciences},
     volume = {26},
     number = {4},
     year = {1992},
     mrnumber = {1173174},
     zbl = {0768.68017},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1992__26_4_345_0/}
}
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
SP  - 345
EP  - 362
VL  - 26
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1992__26_4_345_0/
LA  - en
ID  - ITA_1992__26_4_345_0
ER  - 
%0 Journal Article
%A Krause, M.
%A Meinel, Ch.
%A Waack, St.
%T Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1992
%P 345-362
%V 26
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1992__26_4_345_0/
%G en
%F ITA_1992__26_4_345_0
Krause, M.; Meinel, Ch.; 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, Volume 26 (1992) no. 4, pp. 345-362. http://archive.numdam.org/item/ITA_1992__26_4_345_0/

[AM86] N. Alon and W. Maass, Meanders, Ramsey Theory and Lower Bounds, Proc. 27th I.E.E.E. FOCS 410-417, 1986.

[Im87] N. Immerman, Nondeterministic Space is Closed Under Complement, Techn. Report 552, Yale Univ., 1987. | MR

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

[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. | MR | Zbl

[Kr91] M. Krause, Lower Bounds for Depth-Restricted Branching programs, Inform. and Comput., 1991, 91, pp. 1-14. | MR | Zbl

[KW91] M. Krause and S. Waack, On Oblivious Branching Programs of Linear Length, Inform. and Comput., 1991, 94, pp. 232-249. | MR | Zbl

[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. | MR | Zbl

[Me88] Ch. Meinel, The Power of Polynomial Size Ω-Branching Programs, Proc. STAC'88, Bordeaux, L.N.C.S. n° 294, pp. 81-90. | MR | Zbl

[Ru81] W. Ruzzo, On Uniform Circuit Complexity, J. Comput. System Sci., 1981, 22, (3), pp. 236-283. | MR | Zbl

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

[Sz87] R. Szelepcsenyi, The Method of Forcing for Nondeterministic Automata, Bulletin of the E.A.T.C.S., 1987, 33, pp. 96-99. | Zbl

[We87] I. Wegener, The Complexity of Boolean Functions, Teubner, Stuttgart, 1987. | MR | Zbl