{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T12:46:47Z","timestamp":1649076407179},"reference-count":17,"publisher":"EDP Sciences","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[1992]]},"DOI":"10.1051\/ita\/1992260605071","type":"journal-article","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T14:59:14Z","timestamp":1486047554000},"page":"507-522","source":"Crossref","is-referenced-by-count":5,"title":["Separating $\\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access"],"prefix":"10.1051","volume":"26","author":[{"given":"Matthias","family":"Krause","sequence":"first","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2011,1,8]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"[A&86] AJTAI M., BABAJ L., HAJNAL P., KOMLOS J., PUDLAK P., R\u00d6DEL V., SZEMEREDI E. and TURAN G., Two Lower Bounds for Branching Programs, Proc. 18 ACM-STOC, 1986, pp. 30-39.","DOI":"10.1145\/12130.12134"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"[AM86] ALON N. and MAASS W., Meanders, Ramsey Theory and Lower Bounds for Branching Programs, Proc. 27th ACM-STOC, 1986, pp. 30-39.","DOI":"10.1109\/SFCS.1986.31"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"[CH89] CAI J. and HEMACHANDRA L., On the Power of Parity Polynomial Time, Proc. STACS'89, Springer Verlag, L.N.C.S., No. 349, pp. 229-239.1027404","DOI":"10.1007\/BFb0028987"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"[Co66] COBHAM H., The Recognisation Problem for Perfect Square, Proc. 7-th I.E.E.E. Symp. on SWAT, 1966, pp. 78-87.","DOI":"10.1109\/SWAT.1966.30"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"[DM89] DAMM C. and MEINEL Ch.. Separating Completely Complexity Classes Related to Polynomial Size \u03a9-Decision Trees, Proc. of FCT'89, L.N.C.S., No. 380, pp. 127-136.10335410756.68039","DOI":"10.1007\/3-540-51498-8_12"},{"key":"R6","unstructured":"[H&87] HAJNAL A., MAASS W., PUDLAK P., SZEGEDY M. and TURAN G., Threshold Circuits of Bounded Depth, Proc. 28 I.E.E.E. Symp. F.O.C.S., pp. 99-110.0801.68052"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"IMMERMAN N., Nondeterministic Space is Closed Under Complement, Techn. Report 552, Yale University, 1987.961049","DOI":"10.1109\/SCT.1988.5270"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"[J86] JUKNA S., Lower Bounds on the Complexity of Local Circuits, Proc. MFCS'86, 1986, L.N.C.S. No. 233, pp. 440-448.0609.94018","DOI":"10.1007\/BFb0016269"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"[KMW88] KRAUSE M., MEINEL Ch. and WAACK S., 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).10234440656.68050","DOI":"10.1007\/BFb0017163"},{"key":"R10","unstructured":"[KMW89] KRAUSE M., WAACK S. and MEINEL Ch., 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.0768.68017"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"[KW88] KRAUSE M. and WAACK S., On Oblivious Branching Programs of Linear Length, Proc. of FCT'89, L.N.C.S., No. 380, pp. 287-296 Inform. Comput. (to appear).11275340756.68042","DOI":"10.1007\/3-540-51498-8_28"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"[M88] MEINEL Ch., The Power of Polynomial Size \u03a9-Branching Programs, Proc. STACS'88, Bordeaux, L.N.C.S. No. 294, pp. 81-90, Inform. Comput. (to appear).9357890644.68074","DOI":"10.1007\/BFb0035834"},{"key":"R13","unstructured":"[M89] MEINEL Ch., Modified Branching Programs and their Computational Power, Berlin, 1988, in L.N.C.S. No. 370.10093670669.68042"},{"key":"R14","unstructured":"[PZ83] PAPADIMITRIOU C. and ZACHOS S., 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.0506.68039"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"[Ru81] Ruzzo W., On Uniform Circuit Complexity, J. Comp. System Sci., 1981, 22, (3), pp. 236-283.6335400462.68013","DOI":"10.1016\/0022-0000(81)90038-6"},{"key":"R16","unstructured":"[S87] SZELEPCSENYI R., The Method of Forcing for Nondeterministic Automata, Bulletin of the E.A.T.C.S., 1987, 33, pp. 96-99.0664.68082"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"[W84] WEGENER I., 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.9352610652.68063","DOI":"10.1145\/42282.46161"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1992260605071\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T05:56:36Z","timestamp":1568786196000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1992260605071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"references-count":17,"journal-issue":{"issue":"6"},"alternative-id":["ita1992260605071"],"URL":"https:\/\/doi.org\/10.1051\/ita\/1992260605071","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}