Separating $\oplus L$ from $L,NL,$ co-$NL$, and $AL=P$ for oblivious Turing machines of linear access

 Access to full text

 Full (PDF)

1. [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. 
2. [AM86] N. ALON and W. MAASS, Meanders, Ramsey Theory and Lower Bounds for Branching Programs, Proc. 27th ACM-STOC, 1986, pp. 30-39. 
3. [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. MR1027404
4. [Co66] H. COBHAM, The Recognisation Problem for Perfect Square, Proc. 7-th I.E.E.E. Symp. on SWAT, 1966, pp. 78-87. 
5. [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. Zbl0756.68039MR1033541
6. [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. Zbl0801.68052
7. [187] N. IMMERMAN, Nondeterministic Space is Closed Under Complement, Techn. Report 552, Yale University, 1987. MR961049
8. [J86] S. JUKNA, Lower Bounds on the Complexity of Local Circuits, Proc. MFCS'86, 1986, L.N.C.S. No. 233, pp. 440-448. Zbl0609.94018
9. [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). Zbl0656.68050MR1023444
10. [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. Zbl0768.68017
11. [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). Zbl0756.68042MR1127534
12. [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). Zbl0644.68074MR935789
13. [M89] Ch. MEINEL, Modified Branching Programs and their Computational Power, Berlin, 1988, in L.N.C.S. No. 370. Zbl0669.68042MR1009367
14. [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. Zbl0506.68039
15. [Ru81] W. Ruzzo, On Uniform Circuit Complexity, J. Comp. System Sci., 1981, 22, (3), pp. 236-283. Zbl0462.68013MR633540
16. [S87] R. SZELEPCSENYI, The Method of Forcing for Nondeterministic Automata, Bulletin of the E.A.T.C.S., 1987, 33, pp. 96-99. Zbl0664.68082
17. [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. Zbl0652.68063MR935261