{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T19:45:27Z","timestamp":1794339927724,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540341666","type":"print"},{"value":"9783540341680","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11753728_20","type":"book-chapter","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T16:17:13Z","timestamp":1146154633000},"page":"178-190","source":"Crossref","is-referenced-by-count":1,"title":["Incremental Branching Programs"],"prefix":"10.1007","author":[{"given":"Anna","family":"G\u00e1l","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Kouck\u00fd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"publisher","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 P. Information and Computation\u00a095, 96\u2013115 (1991)","journal-title":"Information and Computation"},{"issue":"4","key":"20_CR2","doi-asserted-by":"publisher","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-Space Tradeoffs for Branching Programs. J. Computer and Systems Science\u00a063(4), 542\u2013572 (2001)","journal-title":"J. Computer and Systems Science"},{"key":"20_CR3","unstructured":"Berkowitz, S.J.: On some relationships between monotone and non-monotone circuit complexity, University of Toronto, Computer Science Department (manuscript, 1981)"},{"issue":"2","key":"20_CR4","doi-asserted-by":"publisher","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. on Computing\u00a011(2), 287\u2013297 (1982)","journal-title":"SIAM J. on Computing"},{"key":"20_CR5","doi-asserted-by":"publisher","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. Computational Complexity\u00a03, 1\u201318 (1993)","journal-title":"Computational Complexity"},{"issue":"1","key":"20_CR6","doi-asserted-by":"publisher","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. of the Association for Computing Machinery\u00a018(1), 4\u201318 (1971)","journal-title":"J. of the Association for Computing Machinery"},{"issue":"3","key":"20_CR7","doi-asserted-by":"publisher","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. Computer and Systems Science\u00a09(3), 308\u2013316 (1974)","journal-title":"J. Computer and Systems Science"},{"key":"20_CR8","doi-asserted-by":"publisher","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. on Computing\u00a09, 636\u2013652 (1980)","journal-title":"SIAM J. on Computing"},{"issue":"6","key":"20_CR9","doi-asserted-by":"publisher","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. on Computing\u00a028(6), 2257\u20132284 (1999)","journal-title":"SIAM J. on Computing"},{"key":"20_CR10","unstructured":"G\u00e1l, A., Kouck\u00fd, M., McKenzie, P.: Incremental branching programs. ECCC TR05-136, 1\u201318 (2005)"},{"key":"20_CR11","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a03, 105\u2013117 (1977)","journal-title":"Theoretical Computer Science"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Jukna, S.: A note on read-k-times branching programs. RAIRO Theoretical Informatics and Applications\u00a029, 75\u201383","DOI":"10.1051\/ita\/1995290100751"},{"key":"#cr-split#-20_CR13.1","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. In: Proc. of the 20th ACM Symp. on the Theory of Computing, pp. 539???550 (1988);","DOI":"10.1145\/62212.62265"},{"key":"#cr-split#-20_CR13.2","doi-asserted-by":"crossref","unstructured":"Full version in: SIAM J. on Disc. Math. 3(2), 255???265 (1990)","DOI":"10.1137\/0403021"},{"key":"20_CR14","doi-asserted-by":"publisher","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. Mathematical Systems Theory\u00a010, 239\u2013251 (1977)","journal-title":"Mathematical Systems Theory"},{"key":"20_CR15","unstructured":"Paterson, M.S., Hewitt, C.E.: Comparative schematology. In: Record of Project MAC Conference on Concurrent Systems and Parallel Computations (June 1970), pp. 119\u2013128. ACM, New Jersey (1970)"},{"key":"20_CR16","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":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/3-540-54458-5_49","volume-title":"Fundamentals of Computation Theory","author":"A. Razborov","year":"1991","unstructured":"Razborov, A.: Lower bounds for deterministic and nondeterministic branching programs. In: Budach, L. (ed.) FCT 1991. LNCS, vol.\u00a0529, pp. 47\u201360. Springer, Heidelberg (1991)"},{"issue":"3","key":"20_CR18","doi-asserted-by":"publisher","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\u00a019(3), 403\u2013435 (1999)","journal-title":"Combinatorica"},{"issue":"2","key":"20_CR19","doi-asserted-by":"publisher","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. Computer and Systems Science\u00a04(2), 177\u2013192 (1970)","journal-title":"J. Computer and Systems Science"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Wegener, I.: The complexity of Boolean functions. Wiley-Teubner (1987)","DOI":"10.1007\/3-540-18170-9_185"},{"key":"20_CR21","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":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11753728_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:03:32Z","timestamp":1619492612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11753728_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540341666","9783540341680"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11753728_20","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11753728","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}