@article{ITA_1992__26_6_507_0, author = {Krause, Matthias}, title = {Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious {Turing} machines of linear access}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {507--522}, publisher = {EDP-Sciences}, volume = {26}, number = {6}, year = {1992}, mrnumber = {1195742}, zbl = {0766.68042}, language = {en}, url = {http://archive.numdam.org/item/ITA_1992__26_6_507_0/} }
TY - JOUR AU - Krause, Matthias TI - Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 1992 SP - 507 EP - 522 VL - 26 IS - 6 PB - EDP-Sciences UR - http://archive.numdam.org/item/ITA_1992__26_6_507_0/ LA - en ID - ITA_1992__26_6_507_0 ER -
%0 Journal Article %A Krause, Matthias %T Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1992 %P 507-522 %V 26 %N 6 %I EDP-Sciences %U http://archive.numdam.org/item/ITA_1992__26_6_507_0/ %G en %F ITA_1992__26_6_507_0
Krause, Matthias. Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 26 (1992) no. 6, pp. 507-522. http://archive.numdam.org/item/ITA_1992__26_6_507_0/
[A&86] Two Lower Bounds for Branching Programs, Proc. 18 ACM-STOC, 1986, pp. 30-39.
, , , , , , and ,[AM86] Meanders, Ramsey Theory and Lower Bounds for Branching Programs, Proc. 27th ACM-STOC, 1986, pp. 30-39.
and ,[CH89] On the Power of Parity Polynomial Time, Proc. STACS'89, Springer Verlag, L.N.C.S., No. 349, pp. 229-239. | MR
and ,[Co66] The Recognisation Problem for Perfect Square, Proc. 7-th I.E.E.E. Symp. on SWAT, 1966, pp. 78-87.
,[DM89] Separating Completely Complexity Classes Related to Polynomial Size Ω-Decision Trees, Proc. of FCT'89, L.N.C.S., No. 380, pp. 127-136. | MR | Zbl
and .[H&87] Threshold Circuits of Bounded Depth, Proc. 28 I.E.E.E. Symp. F.O.C.S., pp. 99-110.
, , , and ,[187] Nondeterministic Space is Closed Under Complement, Techn. Report 552, Yale University, 1987. | MR
,[J86] Lower Bounds on the Complexity of Local Circuits, Proc. MFCS'86, 1986, L.N.C.S. No. 233, pp. 440-448. | Zbl
,[KMW88] Separating the Eraser Turing Machine Classes L, NL, co-NL and P, Proc. of M.F.C.S.'88, Lect. Notes in Compct. Sci, No. 324, pp. 405-413, Theoret. Comput. Sci. (to appear). | MR | Zbl
, and ,[KMW89] Separating Complexity Classes Related to Certain Input-Oblivious Logarithmic-Space Bounded Turing-Machines, Proc. I.E.E.E. Structure & Complexity, 1989, Eugenie, U.S.A.
, and ,[KW88] On Oblivious Branching Programs of Linear Length, Proc. of FCT'89, L.N.C.S., No. 380, pp. 287-296 Inform. Comput. (to appear). | MR | Zbl
and ,[M88] The Power of Polynomial Size Ω-Branching Programs, Proc. STACS'88, Bordeaux, L.N.C.S. No. 294, pp. 81-90, Inform. Comput. (to appear). | MR | Zbl
,[M89] Modified Branching Programs and their Computational Power, Berlin, 1988, in L.N.C.S. No. 370. | MR | Zbl
,[PZ83] Two Remarks on the Power of Counting, Proc. 6 th GI Conf. on Theor. Comp. Sci., Springer Verlag, L.N.C.S., No. 145 pp. 269-276. | Zbl
and ,[Ru81] On Uniform Circuit Complexity, J. Comp. System Sci., 1981, 22, (3), pp. 236-283. | MR | Zbl
,[S87] The Method of Forcing for Nondeterministic Automata, Bulletin of the E.A.T.C.S., 1987, 33, pp. 96-99. | Zbl
,[W84] On the Complexity of Branching Programs and Decision Trees for Clique Functions, Interner Bericht der Univ. Frankfurt, 1984, in J. of the A.C.M., 1988, 35, pp. 461-471. | MR | Zbl
,