{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T03:19:23Z","timestamp":1672975163873},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,9,28]],"date-time":"2007-09-28T00:00:00Z","timestamp":1190937600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,8]]},"DOI":"10.1007\/s00224-007-9049-y","type":"journal-article","created":{"date-parts":[[2007,9,27]],"date-time":"2007-09-27T15:44:23Z","timestamp":1190907863000},"page":"159-184","source":"Crossref","is-referenced-by-count":5,"title":["Incremental Branching Programs"],"prefix":"10.1007","volume":"43","author":[{"given":"Anna","family":"G\u00e1l","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Kouck\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,9,28]]},"reference":[{"key":"9049_CR1","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0890-5401(91)90017-V","volume":"95","author":"D. Barrington","year":"1991","unstructured":"Barrington, D., McKenzie, P.: Oracle branching programs and logspace versus\u00a0P. Inf. Comput. 95, 96\u2013115 (1991)","journal-title":"Inf. Comput."},{"issue":"4","key":"9049_CR2","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1006\/jcss.2001.1778","volume":"63","author":"P. Beame","year":"2001","unstructured":"Beame, P., Jayram, T.S., Saks, M.E.: Time\u2013space tradeoffs for branching programs. J.\u00a0Comput. Syst. Sci. 63(4), 542\u2013572 (2001)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9049_CR3","unstructured":"Berkowitz, S.J.: On some relationships between monotone and non-monotone circuit complexity. Manuscript, Computer Science Department, University of Toronto (1981)"},{"issue":"2","key":"9049_CR4","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A. Borodin","year":"1982","unstructured":"Borodin, A., Cook, S.A.: A time-space trade-off for sorting on a general sequential model of computation. SIAM J.\u00a0Comput. 11(2), 287\u2013297 (1982)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9049_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"Borodin, A., Razborov, A., Smolensky, R.: On lower bounds for read-k-times branching programs. Comput. Complex. 3, 1\u201318 (1993)","journal-title":"Comput. Complex."},{"issue":"1","key":"9049_CR6","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S.A. Cook","year":"1971","unstructured":"Cook, S.A.: Characterizations of pushdown machines in terms of time-bounded computers. J.\u00a0Assoc. Comput. Mach. 18(1), 4\u201318 (1971)","journal-title":"J.\u00a0Assoc. Comput. Mach."},{"issue":"3","key":"9049_CR7","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(74)80046-2","volume":"9","author":"S.A. Cook","year":"1974","unstructured":"Cook, S.A.: An observation on time-storage trade-off. J.\u00a0Comput. Syst. Sci. 9(3), 308\u2013316 (1974)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9049_CR8","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1137\/0209048","volume":"9","author":"S.A. Cook","year":"1980","unstructured":"Cook, S.A., Rackoff, C.W.: Space lower bounds for maze threadability on restricted machines. SIAM J.\u00a0Comput. 9, 636\u2013652 (1980)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"6","key":"9049_CR9","doi-asserted-by":"crossref","first-page":"2257","DOI":"10.1137\/S0097539795295948","volume":"28","author":"J. Edmonds","year":"1999","unstructured":"Edmonds, J., Poon, C.K., Achlioptas, D.: Tight lower bounds for st-connectivity on the NNJAG model. SIAM J.\u00a0Comput. 28(6), 2257\u20132284 (1999)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9049_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1007\/11753728_20","volume-title":"Proc. of the 2006 Computer Science in Russia Conference (CSR06)","author":"A. G\u00e1l","year":"2006","unstructured":"G\u00e1l, A., Kouck\u00fd, M., McKenzie, P.: Incremental branching programs. In: Proc. of the 2006 Computer Science in Russia Conference (CSR06). Lecture Notes in Computer Science, vol.\u00a03967, pp.\u00a0178\u2013190. Springer, Berlin (2006). See also ECCC TR05-136 (2005), pp.\u00a01\u201318"},{"key":"9049_CR11","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N.D. Jones","year":"1977","unstructured":"Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time. Theor. Comput. Sci. 3, 105\u2013117 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"9049_CR12","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1051\/ita\/1995290100751","volume":"29","author":"S. Jukna","year":"1995","unstructured":"Jukna, S.: A note on read-k-times branching programs RAIRO Theor. Inform. Appl. 29, 75\u201383 (1995)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"9049_CR13","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01683275","volume":"10","author":"W.J. Paul","year":"1977","unstructured":"Paul, W.J., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. Math. Syst. Theory 10, 239\u2013251 (1977)","journal-title":"Math. Syst. Theory"},{"key":"9049_CR14","first-page":"119","volume-title":"Record of Project MAC Conference on Concurrent Systems and Parallel Computations","author":"M.S. Paterson","year":"1970","unstructured":"Paterson, M.S., Hewitt, C.E.: Comparative schematology. In: Record of Project MAC Conference on Concurrent Systems and Parallel Computations, June\u00a01970, pp.\u00a0119\u2013128. ACM, New Jersey (1970)"},{"key":"9049_CR15","doi-asserted-by":"crossref","unstructured":"Poon, C.K.: Space bounds for graph connectivity problems on node-named JAGs and node-ordered JAGs. In: Proc. of the 34th IEEE Symp. on the Foundations of Computer Science, pp. 218\u2013227 (1993)","DOI":"10.1109\/SFCS.1993.366865"},{"key":"9049_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-54458-5_49","volume-title":"Proceedings of the 8th FCT","author":"A. Razborov","year":"1991","unstructured":"Razborov, A.: Lower bounds for deterministic and nondeterministic branching programs. In: Proceedings of the 8th FCT. Lecture Notes in Computer Science, vol.\u00a0529, pp.\u00a047\u201360. Springer, Berlin (1991)"},{"issue":"3","key":"9049_CR17","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/s004930050062","volume":"19","author":"R. Raz","year":"1999","unstructured":"Raz, R., McKenzie, P.: Separation of the monotone NC hierarchy. Combinatorica 19(3), 403\u2013435 (1999)","journal-title":"Combinatorica"},{"issue":"2","key":"9049_CR18","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J.\u00a0Comput. Syst. Sci. 4(2), 177\u2013192 (1970)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9049_CR19","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Wiley\u2013Teubner, New York (1987)"},{"key":"9049_CR20","doi-asserted-by":"crossref","unstructured":"Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM Monographs on Discrete Mathematics and Applications (2000)","DOI":"10.1137\/1.9780898719789"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9049-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9049-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9049-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:34Z","timestamp":1558684294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9049-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,28]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["9049"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9049-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,28]]}}}