{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:44Z","timestamp":1740109424535,"version":"3.37.3"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T00:00:00Z","timestamp":1560124800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T00:00:00Z","timestamp":1560124800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s00224-019-09930-2","type":"journal-article","created":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T08:02:54Z","timestamp":1560153774000},"page":"861-914","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Connecting Knowledge Compilation Classes Width Parameters"],"prefix":"10.1007","volume":"64","author":[{"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[]},{"given":"Florent","family":"Capelli","sequence":"additional","affiliation":[]},{"given":"Mika\u00ebl","family":"Monet","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7909-5369","authenticated-orcid":false,"given":"Pierre","family":"Senellart","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,10]]},"reference":[{"unstructured":"Amarilli, A., Bourhis, P., Jachiet, L., Mengel, S.: A circuit-based approach to efficient enumeration. In: ICALP (2017)","key":"9930_CR1"},{"unstructured":"Amarilli, A., Bourhis, P., Monet, M., Senellart, P.: Combined tractability of query evaluation via tree automata and cycluits. In: ICDT (2017)","key":"9930_CR2"},{"doi-asserted-by":"crossref","unstructured":"Amarilli, A., Bourhis, P., Senellart, P.: Provenance circuits for trees and treelike instances. In: ICALP (2015)","key":"9930_CR3","DOI":"10.1007\/978-3-662-47666-6_5"},{"doi-asserted-by":"crossref","unstructured":"Amarilli, A., Bourhis, P., Senellart, P.: Tractable lineages on treelike instances: limits and extensions. In: PODS (2016)","key":"9930_CR4","DOI":"10.1145\/2902251.2902301"},{"unstructured":"Amarilli, A., Monet, M., Senellart, P.: Connecting width and structure in knowledge compilation. In: ICDT (2018)","key":"9930_CR5"},{"unstructured":"Beame, P., Li, J., Roy, S., Suciu, D.: Lower bounds for exact model counting and applications in probabilistic databases. In: UAI (2013)","key":"9930_CR6"},{"issue":"1","key":"9930_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2984632","volume":"42","author":"P Beame","year":"2017","unstructured":"Beame, P., Li, J., Roy, S., Suciu, D.: Exact model counting of query expressions: Limitations of propositional methods. ACM Trans. Database Syst. (TODS) 42(1), 1 (2017)","journal-title":"ACM Trans. Database Syst. (TODS)"},{"unstructured":"Beame, P., Liew, V.: New limits for knowledge compilation and applications to exact model counting. In: UAI (2015)","key":"9930_CR8"},{"issue":"6","key":"9930_CR9","doi-asserted-by":"publisher","first-page":"1305?","DOI":"10.1137\/S0097539793251219","volume":"5","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 5(6), 1305?-1317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9930_CR10","doi-asserted-by":"publisher","first-page":"317?","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A ck n 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317?-378 (2016)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Bollig, B., Buttkus, M.: On the relative succinctness of sentential decision diagrams. arXiv: 1802.04544 (2018)","key":"9930_CR11","DOI":"10.1007\/s00224-018-9904-z"},{"doi-asserted-by":"crossref","unstructured":"Bollig, B., Wegener, I.: Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams. In: MFCS (1997)","key":"9930_CR12","DOI":"10.1007\/BFb0029959"},{"doi-asserted-by":"crossref","unstructured":"Bova, S.: SDDs are exponentially more succinct than OBDDs. In: AAAI (2016)","key":"9930_CR13","DOI":"10.1609\/aaai.v30i1.10107"},{"unstructured":"Bova, S., Capelli, F., Mengel, S., Slivovsky, F.: Knowledge compilation meets communication complexity. In: IJCAI (2016)","key":"9930_CR14"},{"doi-asserted-by":"crossref","unstructured":"Bova, S., Slivovsky, F.: On compiling structured CNFs to OBDDs. In: International Computer Science Symposium in Russia, pp 80\u201393. Springer (2015)","key":"9930_CR15","DOI":"10.1007\/978-3-319-20297-6_6"},{"doi-asserted-by":"crossref","unstructured":"Bova, S., Szeider, S.: Circuit treewidth, sentential decision, and query compilation. In: PODS (2017)","key":"9930_CR16","DOI":"10.1145\/3034786.3034787"},{"issue":"2","key":"9930_CR17","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1109\/12.73590","volume":"40","author":"RE Bryant","year":"1991","unstructured":"Bryant, R.E.: On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication. IEEE Trans. Comput. 40(2), 205\u2013213 (1991)","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"9930_CR18","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."},{"unstructured":"Cal\u00ed, A., Capelli, F., Razgon, I.: Non-FPT lower bounds for structural restrictions of decision DNNF. arXiv: 1708.07767v1 (2017)","key":"9930_CR19"},{"key":"9930_CR20","volume-title":"Structural restrictions of CNF-formulas: Applications to model counting and knowledge compilation","author":"F Capelli","year":"2016","unstructured":"Capelli, F.: Structural restrictions of CNF-formulas: Applications to model counting and knowledge compilation. Ph.D. thesis, Universit\u00e9 Paris-Diderot (2016)"},{"doi-asserted-by":"crossref","unstructured":"Capelli, F.: Understanding the complexity of #SAT using knowledge compilation. In: LICS (2017)","key":"9930_CR21","DOI":"10.1109\/LICS.2017.8005121"},{"unstructured":"Capelli, F., Mengel, S.: Tractable QBF by knowledge compilation. In: STACS (2019)","key":"9930_CR22"},{"unstructured":"Capelli, F., Strozecki, Y.: Enumerating models of DNF faster: Breaking the dependency on the formula size. arXiv: 1810.04006 (2018)","key":"9930_CR23"},{"doi-asserted-by":"crossref","unstructured":"Creignou, N., Olive, F., Schmidt, J.: Enumerating all solutions of a Boolean CSP by non-decreasing weight. In: SAT (2011)","key":"9930_CR24","DOI":"10.1007\/978-3-642-21581-0_11"},{"issue":"4","key":"9930_CR25","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1145\/502090.502091","volume":"48","author":"A Darwiche","year":"2001","unstructured":"Darwiche, A.: Decomposable negation normal form. JACM 48(4), 608\u2013647 (2001)","journal-title":"JACM"},{"issue":"1-2","key":"9930_CR26","doi-asserted-by":"publisher","first-page":"11","DOI":"10.3166\/jancl.11.11-34","volume":"11","author":"A Darwiche","year":"2001","unstructured":"Darwiche, A.: On the tractable counting of theory models and its application to truth maintenance and belief revision. J. Appl. Non-Classical Logics 11(1-2), 11\u201334 (2001)","journal-title":"J. Appl. Non-Classical Logics"},{"issue":"3","key":"9930_CR27","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1145\/765568.765570","volume":"50","author":"A Darwiche","year":"2003","unstructured":"Darwiche, A.: A differential approach to inference in Bayesian networks. JACM 50(3), 280\u2013305 (2003)","journal-title":"JACM"},{"unstructured":"Darwiche, A.: SDD: A new canonical representation of propositional knowledge bases. In: IJCAI (2011)","key":"9930_CR28"},{"key":"9930_CR29","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1613\/jair.989","volume":"17","author":"A Darwiche","year":"2002","unstructured":"Darwiche, A., Marquis, P.: A knowledge compilation map. JAIR 17, 229\u2013264 (2002)","journal-title":"JAIR"},{"issue":"5","key":"9930_CR30","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1109\/43.277617","volume":"12","author":"S Devadas","year":"1993","unstructured":"Devadas, S.: Comparing two-level and ordered binary decision diagram representations of logic functions. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 12(5), 722\u2013723 (1993)","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"issue":"3","key":"9930_CR31","first-page":"358","volume":"15","author":"D Fierens","year":"2015","unstructured":"Fierens, D., den Broeck, G.V., Renkens, J., Shterionov, D., Gutmann, B., Thon, I., Janssens, G., Raedt, L.D.: Inference and learning in probabilistic logic programs using weighted Boolean formulas. TPLP 15(3), 358\u2013401 (2015)","journal-title":"TPLP"},{"issue":"1","key":"9930_CR32","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.jctb.2008.06.004","volume":"99","author":"M Grohe","year":"2009","unstructured":"Grohe, M., Marx, D.: On tree width, bramble size, and expansion. J. Combinatorial Theory Series B 99(1), 218\u2013228 (2009)","journal-title":"J. Combinatorial Theory Series B"},{"doi-asserted-by":"crossref","unstructured":"Jha, A.K., Olteanu, D., Suciu, D.: Bridging the gap between intensional and extensional query evaluation in probabilistic databases. In: EDBT (2010)","key":"9930_CR33","DOI":"10.1145\/1739041.1739082"},{"doi-asserted-by":"crossref","unstructured":"Jha, A.K., Suciu, D.: On the tractability of query compilation and bounded treewidth. In: ICDT (2012)","key":"9930_CR34","DOI":"10.1145\/2274576.2274603"},{"issue":"3","key":"9930_CR35","first-page":"403","volume":"52","author":"AK Jha","year":"2013","unstructured":"Jha, A.K., Suciu, D.: Knowledge compilation meets database theory: Compiling queries to decision diagrams. TCS 52(3), 403\u2013?440 (2013)","journal-title":"TCS"},{"doi-asserted-by":"crossref","unstructured":"Lauritzen, S.L., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. J. Royal Statistical Society Series B (1988)","key":"9930_CR36","DOI":"10.1111\/j.2517-6161.1988.tb01721.x"},{"unstructured":"Meinel, C., Theobald, T.: Algorithms and Data Structures in VLSI Design: OBDD-foundations and applications. Springer Science & Business Media (2012)","key":"9930_CR37"},{"unstructured":"Monet, M., Olteanu, D.: Towards deterministic decomposable circuits for safe queries. In: AMW (2018)","key":"9930_CR38"},{"key":"9930_CR39","volume-title":"Exploring graph parameters similar to tree-width and path-width","author":"JA Nordstrand","year":"2017","unstructured":"Nordstrand, J.A.: Exploring graph parameters similar to tree-width and path-width. University of Bergen, Master\u2019s thesis (2017)"},{"unstructured":"Pipatsrisawat, K., Darwiche, A.: New compilation languages based on structured decomposability. In: AAAI (2008)","key":"9930_CR40"},{"doi-asserted-by":"crossref","unstructured":"Pipatsrisawat, K., Darwiche, A.: A lower bound on the size of decomposable negation normal form. In: AAAI (2010)","key":"9930_CR41","DOI":"10.1609\/aaai.v24i1.7600"},{"key":"9930_CR42","volume-title":"Reasoning with propositional knowledge: Frameworks for Boolean satisfiability and knowledge compilation","author":"T Pipatsrisawat","year":"2010","unstructured":"Pipatsrisawat, T.: Reasoning with propositional knowledge: Frameworks for Boolean satisfiability and knowledge compilation. Ph.D. thesis, University of California (2010)"},{"unstructured":"Razgon, I.: On OBDDs for CNFs of bounded treewidth. In: KR (2014)","key":"9930_CR43"},{"doi-asserted-by":"crossref","unstructured":"Razgon, I.: No small nondeterministic read-once branching programs for CNFs of bounded treewidth. In: IPEC (2014)","key":"9930_CR44","DOI":"10.1007\/978-3-319-13524-3_27"},{"issue":"2","key":"9930_CR45","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.: Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory Series B 52(2), 153\u2013190 (1991)","journal-title":"Journal of Combinatorial Theory Series B"},{"issue":"1\u20133","key":"9930_CR46","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0304-3975(02)00568-6","volume":"301","author":"M Sauerhoff","year":"2003","unstructured":"Sauerhoff, M.: Approximation of boolean functions by combinatorial rectangles. Theor. Comput. Sci. 301(1\u20133), 45\u201378 (2003)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: Communication complexity theory: Thirty-five years of set disjointness. In: MFCS (2014)","key":"9930_CR47","DOI":"10.1007\/978-3-662-44522-8_3"},{"key":"9930_CR48","first-page":"7","volume-title":"Enumeration complexity and matroid decomposition","author":"Y Strozecki","year":"2010","unstructured":"Strozecki, Y.: Enumeration complexity and matroid decomposition, p 7. Ph.D. Thesis, Paris (2010)"},{"doi-asserted-by":"crossref","unstructured":"Suciu, D., Olteanu, D., R\u00e9, C., Koch, C.: Probabilistic databases. Morgan & Claypool (2011)","key":"9930_CR49","DOI":"10.2200\/S00362ED1V01Y201105DTM016"},{"doi-asserted-by":"crossref","unstructured":"Szeider, S.: On fixed-parameter tractable parameterizations of SAT. In: SAT (2004)","key":"9930_CR50","DOI":"10.1007\/978-3-540-24605-3_15"},{"key":"9930_CR51","volume-title":"The complexity of Boolean functions","author":"I Wegener","year":"1991","unstructured":"Wegener, I.: The complexity of Boolean functions. Wiley, New York (1991)"},{"doi-asserted-by":"crossref","unstructured":"Wegener, I.: Branching programs and binary decision diagrams: Theory and applications. SIAM (2000)","key":"9930_CR52","DOI":"10.1137\/1.9780898719789"}],"updated-by":[{"updated":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T00:00:00Z","timestamp":1579910400000},"DOI":"10.1007\/s00224-020-09971-y","type":"correction","source":"publisher","label":"Correction"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09930-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09930-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09930-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,20]],"date-time":"2022-09-20T03:04:17Z","timestamp":1663643057000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09930-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,10]]},"references-count":52,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["9930"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09930-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2019,6,10]]},"assertion":[{"value":"10 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2020","order":2,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The article title in the original publication contains an error. The correct title is presented in this Erratum. The online version of the original article can be found at: https:\/\/doi.org\/10.1007\/s00224-019-09930-2<\/RefSource><\/ExternalRef>","order":4,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}