Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 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},
     zbl = {0768.68017},
     mrnumber = {1173174},
     language = {en},
     url = {http://www.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
DA  - 1992///
SP  - 345
EP  - 362
VL  - 26
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1992__26_4_345_0/
UR  - https://zbmath.org/?q=an%3A0768.68017
UR  - https://www.ams.org/mathscinet-getitem?mr=1173174
LA  - en
ID  - ITA_1992__26_4_345_0
ER  - 
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, Tome 26 (1992) no. 4, pp. 345-362. http://www.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 961049

[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 1122791 | Zbl 0749.68036

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

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

[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 935269 | Zbl 0611.03021

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

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

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

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