{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:30Z","timestamp":1759638270722},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319092836"},{"type":"electronic","value":"9783319092843"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09284-3_29","type":"book-chapter","created":{"date-parts":[[2014,7,2]],"date-time":"2014-07-02T05:43:21Z","timestamp":1404279801000},"page":"399-414","source":"Crossref","is-referenced-by-count":3,"title":["Hypergraph Acyclicity and Propositional Model Counting"],"prefix":"10.1007","author":[{"given":"Florent","family":"Capelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"Durand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Mengel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"29_CR1","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"Booth, K., Lueker, G.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences\u00a013(3), 335\u2013379 (1976), \n                      \n                        http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000076800451","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"29_CR2","first-page":"273","volume":"67","author":"A. Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Combinatoria\u00a067(1), 273\u2013281 (2003)","journal-title":"Ars Combinatoria"},{"key":"29_CR3","unstructured":"Brault-Baron, J.: A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic. In: Computer Science Logic, 26th International Workshop\/21st Annual Conference of the EACSL, pp. 137\u2013151 (2012)"},{"key":"29_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-642-04244-7_24","volume-title":"Principles and Practice of Constraint Programming - CP 2009","author":"D.A. Cohen","year":"2009","unstructured":"Cohen, D.A., Green, M.J., Houghton, C.: Constraint representations and structural tractability. In: Gent, I.P. (ed.) CP 2009. LNCS, vol.\u00a05732, pp. 289\u2013303. Springer, Heidelberg (2009), \n                      \n                        http:\/\/dl.acm.org\/citation.cfm?id=1788994.1789021"},{"issue":"16","key":"29_CR5","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/j.ipl.2012.05.005","volume":"112","author":"D. Duris","year":"2012","unstructured":"Duris, D.: Some characterizations of \u03b3 and \u03b2-acyclicity of hypergraphs. Inf. Process. Lett.\u00a0112(16), 617\u2013620 (2012)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"29_CR6","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/2402.322390","volume":"30","author":"R. Fagin","year":"1983","unstructured":"Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. Journal of the ACM\u00a030(3), 514\u2013550 (1983)","journal-title":"Journal of the ACM"},{"issue":"4","key":"29_CR7","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.dam.2006.06.020","volume":"156","author":"E. Fischer","year":"2008","unstructured":"Fischer, E., Makowsky, J.A., Ravve, E.V.: Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Applied Mathematics\u00a0156(4), 511\u2013529 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"29_CR8","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer-Verlag New York Inc. (2006)"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Pichler, R.: Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width. SIAM Journal on Computing\u00a033(2) (2004)","DOI":"10.1137\/S0097539701396807"},{"key":"29_CR10","unstructured":"Mikl\u00f3s, Z.: Understanding Tractable Decompositions for Constraint Satisfaction. Ph.D. thesis. University of Oxford (2008)"},{"key":"29_CR11","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0481, 85\u201399 (2013)","journal-title":"Theoretical Computer Science"},{"key":"29_CR12","unstructured":"Paulusma, D., Slivovsky, F., Szeider, S.: Model Counting for CNF Formulas of Bounded Modular Treewidth. In: 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, pp. 55\u201366 (2013)"},{"issue":"1-2","key":"29_CR13","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","volume":"82","author":"D. Roth","year":"1996","unstructured":"Roth, D.: On the hardness of approximate reasoning. Artificial Intelligence\u00a082(1-2), 273\u2013302 (1996), \n                      \n                        http:\/\/www.sciencedirect.com\/science\/article\/pii\/0004370294000921","journal-title":"Artificial Intelligence"},{"issue":"1","key":"29_CR14","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.jda.2009.06.002","volume":"8","author":"M. Samer","year":"2010","unstructured":"Samer, M., Szeider, S.: Algorithms for propositional model counting. Journal of Discrete Algorithms\u00a08(1), 50\u201364 (2010)","journal-title":"Journal of Discrete Algorithms"},{"key":"29_CR15","unstructured":"Slivovsky, F.: Personal communication (2014)"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Slivovsky, F., Szeider, S.: Model Counting for Formulas of Bounded Clique-Width. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) ISAAC 2013. LNCS, vol.\u00a08283, pp. 677\u2013687. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-45030-3_63"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09284-3_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T01:55:17Z","timestamp":1558922117000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-09284-3_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319092836","9783319092843"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09284-3_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}