Separating ⊕L from L,NL, co-NL, and AL=P for oblivious Turing machines of linear access
Krause, Matthias
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 26 (1992), p. 507-522 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1992-01-01
@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},
     volume = {26},
     year = {1992},
     pages = {507-522},
     mrnumber = {1195742},
     zbl = {0766.68042},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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, Tome 26 (1992) pp. 507-522. http://gdmltest.u-ga.fr/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 1027404

[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 1033541 | Zbl 0756.68039

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

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

[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 1023444 | Zbl 0656.68050

[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 1127534 | Zbl 0756.68042

[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 935789 | Zbl 0644.68074

[M89] Ch. Meinel, Modified Branching Programs and their Computational Power, Berlin, 1988, in L.N.C.S. No. 370. | MR 1009367 | Zbl 0669.68042

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

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

[S87] 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

[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 935261 | Zbl 0652.68063