{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:52:56Z","timestamp":1725663176262},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514862"},{"type":"electronic","value":"9783540481768"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51486-4_84","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:58:20Z","timestamp":1330203500000},"page":"370-379","source":"Crossref","is-referenced-by-count":2,"title":["Oracle branching programs and Logspace versus P"],"prefix":"10.1007","author":[{"given":"David A. Mix","family":"Barrington","sequence":"first","affiliation":[]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"R. Aleliunas, R. Karp, R. Lipton, L. Lovasz and C. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, Proc. of the 20th IEEE Symp. on the Foundations of Computer Science (1979), pp. 218\u2013233.","DOI":"10.1109\/SFCS.1979.34"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"D.A. Mix Barrington and P. McKenzie, Oracle branching programs and Logspace versus P, Rapport technique #672, DIRO, Univ. de Montr\u00e9al, 1989.","DOI":"10.1007\/3-540-51486-4_84"},{"key":"32_CR3","doi-asserted-by":"crossref","unstructured":"A. Borodin, D. Dolev, F. Fich and W. Paul, Bounds for width-two branching programs, Proc. of the 15th ACM Symp. on the Theory of Computing (1983), pp. 97\u201393.","DOI":"10.1145\/800061.808736"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"A. Borodin, M.J. Fisher, D.G. Kirkpatrick, N.A. Lynch and M. Tompa, A time-space tradeoff for sorting on non-oblivious machines, Proc. of the 20th IEEE Symp. on the Foundations of Computer Science (1979), pp. 319\u2013327.","DOI":"10.1109\/SFCS.1979.4"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"A. Chandra, M. Furst and R. Lipton, Multi-party protocols, Proc. of the 15th ACM Symp. on the Theory of Computing (1983), pp. 94\u201399.","DOI":"10.1145\/800061.808737"},{"issue":"3","key":"32_CR6","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(74)80046-2","volume":"9","author":"S. A. Cook","year":"1974","unstructured":"S.A. Cook, An observation on time-storage trade-off, J. Computer and Systems ScienceVol. 9, no. 3 (1974), pp. 308\u2013316.","journal-title":"J. Computer and Systems Science"},{"key":"32_CR7","unstructured":"S.A. Cook, Towards a complexity theory of synchronous parallel computation, in L'enseignement math\u00e9matique, S\u00e9rie II, Tome XXVII, fasc. 1\u20132 (1981)."},{"key":"32_CR8","first-page":"2","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S.A. Cook, A taxonomy of problems with fast parallel solutions, Information and Computation64 (1985), pp. 2\u201322.","journal-title":"Information and Computation"},{"key":"32_CR9","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"S. A. Cook","year":"1987","unstructured":"S.A. Cook and P. McKenzie, Problems complete for deterministic logarithmic space, J. of Algorithms8 (1987), pp. 385\u2013394.","journal-title":"J. of Algorithms"},{"key":"32_CR10","unstructured":"J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley (1979)."},{"key":"32_CR11","unstructured":"N. Immerman, Nondeterministic space is closed under complement, Proc. of the 3rd Structure in Complexity Conference (1988), IEEE Computer Society Press, pp. 112\u2013115."},{"key":"32_CR12","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. D. Jones","year":"1975","unstructured":"N.D. Jones, Space-bounded reducibility among combinatorial problems, J. Computer and Systems Science11 (1975), pp. 68\u201385.","journal-title":"J. Computer and Systems Science"},{"key":"32_CR13","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. D. Jones","year":"1977","unstructured":"N.D. Jones and W.T. Laaser, Complete problems for deterministic polynomial time, Theoretical Computer Science3 (1977), pp. 105\u2013117.","journal-title":"Theoretical Computer Science"},{"key":"32_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"N. D. Jones","year":"1976","unstructured":"N.D. Jones, E. Lien and W.T. Laaser, New problems complete for nondeterministic log space, Math. Systems Theory10 (1976), pp. 1\u201317.","journal-title":"Math. Systems Theory"},{"key":"32_CR15","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0022-0000(88)90027-X","volume":"36","author":"R. Karp","year":"1988","unstructured":"R. Karp, E. Upfal and A. Wigderson, The complexity of parallel search, J. Computer and Systems Science36 (1988), pp. 225\u2013253.","journal-title":"J. Computer and Systems Science"},{"key":"32_CR16","doi-asserted-by":"crossref","unstructured":"D. Kozen, Lower bounds for natural proof systems, Proc. of the 18th ACM Symp. on the Theory of Computing (1977), pp. 254\u2013266.","DOI":"10.1109\/SFCS.1977.16"},{"issue":"1","key":"32_CR17","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R. E. Lander","year":"1975","unstructured":"R.E. Lander, The circuit value problem is log space somplete for P, SIGACT News7 No. 1 (1975), pp. 18\u201320.","journal-title":"SIGACT News"},{"key":"32_CR18","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1002\/j.1538-7305.1959.tb01585.x","volume":"38","author":"C. Y. Lee","year":"1959","unstructured":"C.Y. Lee Representation of switching functions by binary decision programs, Bell Systems Technical Journal 38 (1959), pp. 985\u2013999.","journal-title":"Bell Systems Technical Journal"},{"key":"32_CR19","unstructured":"W. Masek, A fast algorithm for the string editing problem and decision graph complexity, M. Sc. Thesis, M.I.T. (May 1976)."},{"key":"32_CR20","first-page":"xx","volume":"xx","author":"P. McKenzie","year":"1989","unstructured":"P. McKenzie and D. Th\u00e9rien, Automata theory meets circuit complexity, Proc. of the 16th International Colloquium on Automata, Languages and Programming, Springer Lecture Notes in Comp. Sci. xx (1989), pp. xx\u2013xx.","journal-title":"Springer Lecture Notes in Comp. Sci."},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"N. Pippenger, On simultaneous resource bounds, Proc. of the 20th IEEE Symp. on the Foundations of Computer Science (1979), pp. 307\u2013311.","DOI":"10.1109\/SFCS.1979.29"},{"key":"32_CR22","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"W.J. Savitch, Relationship between nondeterministic and deterministic tape complexities, J. Computer and Systems Science4 (1970), pp. 177\u2013192.","journal-title":"J. Computer and Systems Science"},{"key":"32_CR23","unstructured":"R. Szelepcs\u00e9nyi, The method of forcing for nondeterministic automata, Bull. European Assoc. for Theor. Comp. Sci. (Oct. 1987), pp. 96\u2013100."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1989"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51486-4_84.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:21:28Z","timestamp":1605648088000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51486-4_84"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514862","9783540481768"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-51486-4_84","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}