@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] Meanders, Ramsey Theory and Lower Bounds, Proc. 27th I.E.E.E. FOCS 410-417, 1986.
and ,[Im87] Nondeterministic Space is Closed Under Complement, Techn. Report 552, Yale Univ., 1987. | MR
,[KL80] Some Connections Between Nonuniform and Uniform Complexity Classes, Proc. 12th A.C.M. Symp. on Theory of Computing, 302-309 1980.
and ,[KMW91] Separating the Eraser Turing Machine Classes Le, NLe, co-NLe and Pe, Theoret. Comput. Sci., 1991, 86, pp. 267-275. | MR | Zbl
, and ,[Kr91] Lower Bounds for Depth-Restricted Branching programs, Inform. and Comput., 1991, 91, pp. 1-14. | MR | Zbl
,[KW91] On Oblivious Branching Programs of Linear Length, Inform. and Comput., 1991, 94, pp. 232-249. | MR | Zbl
and ,[Me86] 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] The Power of Polynomial Size Ω-Branching Programs, Proc. STAC'88, Bordeaux, L.N.C.S. n° 294, pp. 81-90. | MR | Zbl
,[Ru81] On Uniform Circuit Complexity, J. Comput. System Sci., 1981, 22, (3), pp. 236-283. | MR | Zbl
,[SV81] A Complexity Theory Based on Boolean Algebra, Proc. 22th LE.E.E. F.O.C.S., 1981, pp. 244-253.
and ,[Sz87] The Method of Forcing for Nondeterministic Automata, Bulletin of the E.A.T.C.S., 1987, 33, pp. 96-99. | Zbl
,[We87] The Complexity of Boolean Functions, Teubner, Stuttgart, 1987. | MR | Zbl
,