{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T23:37:04Z","timestamp":1790465824800,"version":"4.1.0"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319409696","type":"print"},{"value":"9783319409702","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-40970-2_1","type":"book-chapter","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T07:14:55Z","timestamp":1465542895000},"page":"3-12","source":"Crossref","is-referenced-by-count":2,"title":["Parameterized Compilation Lower Bounds for\u00a0Restricted CNF-Formulas"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Mengel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,6,11]]},"reference":[{"key":"1_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/978-3-319-24318-4_15","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2015","author":"S Bova","year":"2015","unstructured":"Bova, S., Capelli, F., Mengel, S., Slivovsky, F.: On compiling CNFs into structured deterministic DNNFs. In: Heule, M., Weaver, S. (eds.) SAT 2015. LNCS, vol. 9340, pp. 199\u2013214. Springer, Heidelberg (2015). doi: 10.1007\/978-3-319-24318-4_15"},{"key":"1_CR2","unstructured":"Bova, S., Capelli, F., Mengel, S., Slivovsky, F.: Knowledge compilation meets communication complexity. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, IJCAI 2016. IJCAI\/AAAI (to appear, 2016)"},{"key":"1_CR3","unstructured":"Brault-Baron, J., Capelli, F., Mengel, S.: Understanding model counting for beta-acyclic CNF-formulas. In: Mayr, E.W., Ollinger, N. (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, Garching, Germany, 4\u20137 March 2015. LIPIcs, vol. 30, pp. 143\u2013156. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)"},{"key":"1_CR4","unstructured":"Chen, H.: Parameterized compilability. In: Kaelbling, L.P., Saffiotti, A. (eds.) Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI 2005, Edinburgh, Scotland, UK, 30 July\u20135 August 2005, pp. 412\u2013417. Professional Book Center (2005)"},{"key":"1_CR5","unstructured":"Chen, H.: Parameter compilation. In: Husfeldt, T., Kanj, I.A. (eds.) 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, Patras, Greece, 16\u201318 September 2015. LIPIcs, vol. 43, pp. 127\u2013137. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)"},{"issue":"4","key":"1_CR6","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1145\/502090.502091","volume":"48","author":"A Darwiche","year":"2001","unstructured":"Darwiche, A.: Decomposable negation normal form. J. ACM 48(4), 608\u2013647 (2001)","journal-title":"J. ACM"},{"key":"1_CR7","unstructured":"Darwiche, A.: New advances in compiling CNF into decomposable negation normal form. In L\u00f3pez de M\u00e1ntaras, R., Saitta, L. (eds.) Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAI 2004, including Prestigious Applicants of Intelligent Systems, PAIS 2004, Valencia, Spain, 22\u201327 August 2004, pp. 328\u2013332. IOS Press (2004)"},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.989","volume":"17","author":"A Darwiche","year":"2002","unstructured":"Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res. (JAIR) 17, 229\u2013264 (2002)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"1_CR9","first-page":"130","volume":"22","author":"R Haan de","year":"2015","unstructured":"de Haan, R.: An overview of non-uniform parameterized complexity. Electron. Colloquium Comput. Complex. (ECCC) 22, 130 (2015)","journal-title":"Electron. Colloquium Comput. Complex. (ECCC)"},{"key":"1_CR10","unstructured":"Dell, H., Kim, E.J., Lampis, M., Mitsou, V., M\u00f6mke, T.: Complexity and approximability of parameterized MAX-CSPs. In: Husfeldt, T., Kanj, I.A. (eds.) 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, Patras, Greece, 16\u201318 September 2015. LIPIcs, vol. 43, pp. 294\u2013306. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)"},{"key":"1_CR11","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)","edition":"4"},{"issue":"1","key":"1_CR12","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.ic.2004.05.002","volume":"194","author":"P Duris","year":"2004","unstructured":"Duris, P., Hromkovic, J., Jukna, S., Sauerhoff, M., Schnitger, G.: On multi-partition communication complexity. Inf. Comput. 194(1), 49\u201375 (2004)","journal-title":"Inf. Comput."},{"key":"1_CR13","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"1_CR14","unstructured":"Huang, J., Darwiche, A.: DPLL with a trace: from SAT to knowledge compilation. In: Kaelbling, L.P., Saffiotti, A. (eds.) Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI 2005, Edinburgh, Scotland, UK, 30 July\u20135 August 2005, pp. 156\u2013162. Professional Book Center (2005)"},{"key":"1_CR15","unstructured":"Koriche, F., Lagniez, J.-M., Marquis, P., Thomas, S.: Compilation, knowledge compilation for model counting : affine decision trees. In Rossi, R. (ed.) Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013, Beijing, China, 3\u20139 August 2013. IJCAI\/AAAI (2013)"},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/978-3-642-15775-2_47","volume-title":"Algorithms \u2013 ESA 2010","author":"M Lampis","year":"2010","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol. 6346, pp. 549\u2013560. Springer, Heidelberg (2010)"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1007\/978-3-642-30353-1_36","volume-title":"Advances in Artificial Intelligence","author":"C Muise","year":"2012","unstructured":"Muise, C., McIlraith, S.A., Beck, J.C., Hsu, E.I.: Dsharp: Fast d-DNNF Compilation with $$\\sf sharpSAT$$ . In: Kosseim, L., Inkpen, D. (eds.) Canadian AI 2012. LNCS, vol. 7310, pp. 356\u2013361. Springer, Heidelberg (2012)"},{"key":"1_CR18","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.tcs.2012.12.039","volume":"481","author":"S Ordyniak","year":"2013","unstructured":"Ordyniak, S., Paulusma, D., Szeider, S.: Satisfiability of acyclic and almost acyclic CNF formulas. Theor. Comput. Sci. 481, 85\u201399 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR19","unstructured":"Paulusma, D., Slivovsky, F., Szeider, S.: Model counting for CNF formulas of bounded modular treewidth. In: Portier, N., Wilke, T. (eds.) 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, Kiel, Germany, 27 February\u20132 March 2013. LIPIcs, vol. 20, pp. 55\u201366. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)"},{"key":"1_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/978-3-319-13524-3_27","volume-title":"Parameterized and Exact Computation","author":"I Razgon","year":"2014","unstructured":"Razgon, I.: No small nondeterministic read-once branching programs for CNFs of bounded treewidth. In: Cygan, M., Heggernes, P. (eds.) IPEC 2014. LNCS, vol. 8894, pp. 319\u2013331. Springer, Heidelberg (2014)"},{"key":"1_CR21","unstructured":"Razgon, I.: On OBDDs for CNFs of bounded treewidth. In: Baral, C., De Giacomo, G., Eiter, T. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, 20\u201324 July 2014. AAAI Press (2014)"},{"key":"1_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/978-3-319-12340-0_33","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"SH S\u00e6ther","year":"2014","unstructured":"S\u00e6ther, S.H., Telle, J.A.: Between treewidth and clique-width. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 396\u2013407. Springer, Heidelberg (2014)"},{"key":"1_CR23","unstructured":"Sang, T., Bacchus, F., Beame, P., Kautz, H.A., Pitassi, T.: Combining component caching and clause learning for effective model counting. In: Proceedings of the Seventh International Conference on Theory and Applications of Satisfiability Testing, SAT 2004, Vancouver, BC, Canada, 10\u201313 May 2004"},{"key":"1_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1007\/11814948_38","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"M Thurley","year":"2006","unstructured":"Thurley, M.: sharpSAT \u2013 counting models with advanced component caching and implicit BCP. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 424\u2013429. Springer, Heidelberg (2006)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2016"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40970-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T10:08:18Z","timestamp":1568023698000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40970-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319409696","9783319409702"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40970-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}