{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T18:22:12Z","timestamp":1743013332955,"version":"3.40.3"},"publisher-location":"Cham","reference-count":9,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319135236"},{"type":"electronic","value":"9783319135243"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13524-3_27","type":"book-chapter","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T17:51:38Z","timestamp":1417542698000},"page":"319-331","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth"],"prefix":"10.1007","author":[{"given":"Igor","family":"Razgon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,3]]},"reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A Borodin","year":"1993","unstructured":"Borodin, A., Razborov, A.A., Smolensky, R.: On lower bounds for read-k-times branching programs. Comput. Complex 3, 1\u201318 (1993)","journal-title":"Comput. Complex"},{"issue":"3","key":"27_CR2","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/136035.136043","volume":"24","author":"RE Bryant","year":"1992","unstructured":"Bryant, R.E.: Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surv. 24(3), 293\u2013318 (1992)","journal-title":"ACM Comput. Surv."},{"key":"27_CR3","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/11591191_34","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"A Ferrara","year":"2005","unstructured":"Ferrara, A., Pan, G., Vardi, M.Y.: Treewidth in verification: Local vs. global. In: Sutcliffe, G., Voronkov, A. (eds.) LPAR 2005. LNCS (LNAI), vol. 3835, pp. 489\u2013503. Springer, Heidelberg (2005)"},{"key":"27_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24508-4","volume-title":"Boolean Function Complexity: Advances and Frontiers","author":"S Jukna","year":"2012","unstructured":"Jukna, S.: Boolean Function Complexity: Advances and Frontiers. Springer, Berlin (2012)"},{"key":"27_CR5","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. 199, pp. 47\u201360. Springer, Heidelberg (1991)"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Razborov, A., Wigderson, A., Chi-Chih Yao, A.: Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. In: STOC, pp. 739\u2013748 (1997)","DOI":"10.1145\/258533.258673"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"Razgon, I.: No small nondeterministic read-once branching programs for CNFs of bounded treewidth. CoRR, abs\/1407.0491 (2014)","DOI":"10.1007\/978-3-319-13524-3_27"},{"key":"27_CR8","unstructured":"Razgon, I.: On OBDDs for CNFs of bounded treewidth. In: KR, pp. 92\u2013100 (2014)"},{"key":"27_CR9","unstructured":"Vatshelle, M.: New width parameters of graphs. Ph.D. Thesis, Department of Informatics, University of Bergen 2012"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13524-3_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T09:18:08Z","timestamp":1674897488000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13524-3_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319135236","9783319135243"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13524-3_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"3 December 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}