{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:22:35Z","timestamp":1760170955156},"reference-count":38,"publisher":"Cambridge University Press (CUP)","issue":"4-5","license":[{"start":{"date-parts":[[2015,9,3]],"date-time":"2015-09-03T00:00:00Z","timestamp":1441238400000},"content-version":"unspecified","delay-in-days":64,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2015,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recent advances in knowledge compilation introduced techniques to compile<jats:italic>positive<\/jats:italic>logic programs into propositional logic, essentially exploiting the constructive nature of the least fixpoint computation. This approach has several advantages over existing approaches: it maintains logical equivalence, does not require (expensive) loop-breaking preprocessing or the introduction of auxiliary variables, and significantly outperforms existing algorithms. Unfortunately, this technique is limited to<jats:italic>negation-free<\/jats:italic>programs. In this paper, we show how to extend it to general logic programs under the well-founded semantics.<\/jats:p><jats:p>We develop our work in approximation fixpoint theory, an algebraical framework that unifies semantics of different logics. As such, our algebraical results are also applicable to autoepistemic logic, default logic and abstract dialectical frameworks.<\/jats:p>","DOI":"10.1017\/s1471068415000162","type":"journal-article","created":{"date-parts":[[2015,9,3]],"date-time":"2015-09-03T08:21:21Z","timestamp":1441268481000},"page":"464-480","source":"Crossref","is-referenced-by-count":4,"title":["Knowledge compilation of logic programs using approximation fixpoint theory"],"prefix":"10.1017","volume":"15","author":[{"given":"BART","family":"BOGAERTS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GUY","family":"VAN DEN BROECK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2015,9,3]]},"reference":[{"key":"S1471068415000162_ref2","doi-asserted-by":"crossref","unstructured":"Antic C. , Eiter T. and Fink M. 2013. Hex semantics via approximation fixpoint theory. In Proceedings of LPNMR. 102\u2013115.","DOI":"10.1007\/978-3-642-40564-8_11"},{"key":"S1471068415000162_ref36","doi-asserted-by":"publisher","DOI":"10.1145\/321978.321991"},{"key":"S1471068415000162_ref23","doi-asserted-by":"publisher","DOI":"10.2307\/2267778"},{"key":"S1471068415000162_ref34","doi-asserted-by":"crossref","unstructured":"Suciu D. , Olteanu D. , R\u00e9 C. and Koch C. 2011. Probabilistic databases.","DOI":"10.2200\/S00362ED1V01Y201105DTM016"},{"key":"S1471068415000162_ref18","unstructured":"Gelfond M. and Lifschitz V. 1988. The stable model semantics for logic programming. In Proceedings of ICLP\/SLP. 1070\u20131080."},{"key":"S1471068415000162_ref30","first-page":"301","article-title":"Well-founded and stable semantics of logic programs with aggregates","volume":"7","author":"Pelov","year":"2007","journal-title":"TPLP"},{"key":"S1471068415000162_ref32","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226644"},{"key":"S1471068415000162_ref19","unstructured":"Huang J. and Darwiche A. 2005. On compiling system models for faster and more scalable diagnosis. In Proceedings of AAAI. 300\u2013306."},{"key":"S1471068415000162_ref10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.989","article-title":"A knowledge compilation map","volume":"17","author":"Darwiche","year":"2002","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"S1471068415000162_ref7","unstructured":"Chavira M. and Darwiche A. 2005. Compiling bayesian networks with local structure. In Proceedings of IJCAI. 1306\u20131312."},{"key":"S1471068415000162_ref5","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"S1471068415000162_ref22","first-page":"142","volume-title":"LPNMR","author":"Janhunen","year":"2009"},{"key":"S1471068415000162_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90032-Z"},{"key":"S1471068415000162_ref25","unstructured":"Lin F. and Zhao J. 2003. On tight logic programs and yet another translation from normal logic programs to propositional logic. In Proceedings of IJCAI. 853\u2013858."},{"key":"S1471068415000162_ref37","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116838"},{"key":"S1471068415000162_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-934613-40-8.50009-9"},{"key":"S1471068415000162_ref24","doi-asserted-by":"publisher","DOI":"10.1145\/1131313.1131316"},{"key":"S1471068415000162_ref27","unstructured":"Lowd D. and Domingos P. 2008. Learning arithmetic circuits. In Proceedings of UAI. 383\u2013392."},{"key":"S1471068415000162_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.11.001"},{"key":"S1471068415000162_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-1567-8_6"},{"key":"S1471068415000162_ref29","unstructured":"Palacios H. , Bonet B. , Darwiche A. and Geffner H. 2005. Pruning conformant plans by counting models on compiled d-dnnf representations. In Proceedings of ICAPS. 141\u2013150."},{"key":"S1471068415000162_ref16","first-page":"358","article-title":"Inference and learning in probabilistic logic programs using weighted boolean formulas","volume":"15","author":"Fierens","year":"2015","journal-title":"TPLP"},{"key":"S1471068415000162_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00330-3"},{"key":"S1471068415000162_ref9","unstructured":"Darwiche A. 2011. SDD: A new canonical representation of propositional knowledge bases. In Proceedings of IJCAI. 819\u2013826."},{"key":"S1471068415000162_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.11.002"},{"key":"S1471068415000162_ref33","first-page":"39","article-title":"Approximating operators and semantics for abstract dialectical frameworks","volume":"205","author":"Strass","year":"2013","journal-title":"AIJ"},{"key":"S1471068415000162_ref20","unstructured":"Janhunen T. 2004. Representing normal programs with clauses. In Proceedings of ECAI. 358\u2013362."},{"key":"S1471068415000162_ref26","first-page":"115","article-title":"ASSAT: Computing answer sets of a logic program by SAT solvers","volume":"157","author":"Lin","year":"2004","journal-title":"AIJ"},{"key":"S1471068415000162_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"S1471068415000162_ref6","first-page":"137","article-title":"A survey on knowledge compilation","volume":"10","author":"Cadoli","year":"1997","journal-title":"AI Commun."},{"key":"S1471068415000162_ref38","unstructured":"Vlasselaer J. , Van den Broeck G. , Kimmig A. , Meert W. and De Raedt L. 2015. Anytime inference in probabilistic logic programs with -compilation. In Proceedings of IJCAI. Available on https:\/\/lirias.kuleuven.be\/handle\/123456789\/494681."},{"key":"S1471068415000162_ref35","doi-asserted-by":"crossref","unstructured":"Van den Broeck G. and Darwiche A. 2015. On the role of canonicity in knowledge compilation. In Proceedings of AAAI.","DOI":"10.1609\/aaai.v29i1.9423"},{"key":"S1471068415000162_ref14","doi-asserted-by":"crossref","unstructured":"Denecker M. and Vennekens J. 2007. Well-founded semantics and the algebraic theory of non-monotone inductive definitions. In LPNMR. 84\u201396.","DOI":"10.1007\/978-3-540-72200-7_9"},{"key":"S1471068415000162_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.02.004"},{"key":"S1471068415000162_ref21","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.16.35-86"},{"key":"S1471068415000162_ref11","unstructured":"Denecker M. , Lierler Y. , Truszczy\u0144ski M. and Vennekens J. 2012. A Tarskian informal semantics for answer set programming. In ICLP (Technical Communications). 277\u2013289."},{"key":"S1471068415000162_ref15","unstructured":"Denecker M. and Vennekens J. 2014. The well-founded semantics is the principle of inductive definition, revisited. In Proceedings of KR. 22\u201331."},{"key":"S1471068415000162_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530761"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068415000162","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,13]],"date-time":"2023-08-13T18:02:27Z","timestamp":1691949747000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068415000162\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7]]},"references-count":38,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["S1471068415000162"],"URL":"https:\/\/doi.org\/10.1017\/s1471068415000162","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7]]}}}