Separating 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.
@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] M. Ajtai, L. Babaj, P. Hajnal, J. Komlos, P. Pudlak, V. Rödel, E. Szemeredi and G. Turan, Two Lower Bounds for Branching Programs, Proc. 18 ACM-STOC, 1986, pp. 30-39.

[AM86] N. Alon and W. Maass, Meanders, Ramsey Theory and Lower Bounds for Branching Programs, Proc. 27th ACM-STOC, 1986, pp. 30-39.

[CH89] J. Cai and L. Hemachandra, On the Power of Parity Polynomial Time, Proc. STACS'89, Springer Verlag, L.N.C.S., No. 349, pp. 229-239. | MR

[Co66] H. Cobham, The Recognisation Problem for Perfect Square, Proc. 7-th I.E.E.E. Symp. on SWAT, 1966, pp. 78-87.

[DM89] C. Damm and Ch. Meinel. 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

[H&87] A. Hajnal, W. Maass, P. Pudlak, M. Szegedy and G. Turan, Threshold Circuits of Bounded Depth, Proc. 28 I.E.E.E. Symp. F.O.C.S., pp. 99-110.

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

[J86] S. Jukna, Lower Bounds on the Complexity of Local Circuits, Proc. MFCS'86, 1986, L.N.C.S. No. 233, pp. 440-448. | Zbl

[KMW88] M. Krause, Ch. Meinel and S. Waack, 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

[KMW89] M. Krause, S. Waack and Ch. Meinel, 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.

[KW88] M. Krause and S. Waack, 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

[M88] Ch. Meinel, 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] Ch. Meinel, Modified Branching Programs and their Computational Power, Berlin, 1988, in L.N.C.S. No. 370. | MR | Zbl

[PZ83] C. Papadimitriou and S. Zachos, 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

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

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

[W84] I. Wegener, 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