{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T01:14:22Z","timestamp":1768439662656,"version":"3.49.0"},"reference-count":50,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2011,12,30]],"date-time":"2011-12-30T00:00:00Z","timestamp":1325203200000},"content-version":"unspecified","delay-in-days":0,"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":[[2013,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Open Answer Set Programming (OASP) is an undecidable framework for integrating ontologies and rules. Although several decidable fragments of OASP have been identified, few reasoning procedures exist. In this paper, we provide a sound, complete, and terminating algorithm for satisfiability checking w.r.t. Forest Logic Programs (FoLPs), a fragment of OASP where rules have a tree shape and allow for inequality atoms and constants. The algorithm establishes a decidability result for FoLPs. Although believed to be decidable, so far only the decidability for two small subsets of FoLPs, local FoLPs and acyclic FoLPs, has been shown. We further introduce f-hybrid knowledge bases, a hybrid framework where<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1471068411000597_char1\"\/><\/jats:private-char>knowledge bases and FoLPs coexist, and we show that reasoning with such knowledge bases can be reduced to reasoning with FoLPs only. We note that f-hybrid knowledge bases do not require the usual (weakly) DL-safety of the rule component, thus providing a genuine alternative approach to current integration approaches of ontologies and rules.<\/jats:p>","DOI":"10.1017\/s1471068411000597","type":"journal-article","created":{"date-parts":[[2011,12,30]],"date-time":"2011-12-30T12:12:04Z","timestamp":1325247124000},"page":"395-463","source":"Crossref","is-referenced-by-count":1,"title":["Reasoning with Forest Logic Programs and f-hybrid knowledge bases"],"prefix":"10.1017","volume":"13","author":[{"given":"CRISTINA","family":"FEIER","sequence":"first","affiliation":[]},{"given":"STIJN","family":"HEYMANS","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2011,12,30]]},"reference":[{"key":"S1471068411000597_ref49","unstructured":"Tobies S. 2001. Complexity Results and Practical Algorithms for Logics in Knowledge Representation. PhD thesis, RWTH-Aachen, Aachen, Germany."},{"key":"S1471068411000597_ref42","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754403"},{"key":"S1471068411000597_ref41","unstructured":"Motik B. and Rosati R. 2006. Closing Semantic Web Ontologies. Tech. Rep., University of Manchester, UK."},{"key":"S1471068411000597_ref39","first-page":"245","volume-title":"Readings in Knowledge Representation","author":"Minsky","year":"1985"},{"key":"S1471068411000597_ref38","first-page":"141","volume-title":"Proceedings of KR-2004","author":"Lukasiewicz","year":"2004"},{"key":"S1471068411000597_ref40","first-page":"501","volume-title":"Proceedings of the International Semantic Web Conference (ISWC)","author":"Motik","year":"2006"},{"key":"S1471068411000597_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00227-8"},{"key":"S1471068411000597_ref36","first-page":"377","volume-title":"Proceedings of the 26th International Conference on Logic Programming (ICLP)","author":"Lierler","year":"2008"},{"key":"S1471068411000597_ref35","first-page":"323","volume-title":"Proceedings of ECAI'96","author":"Levy","year":"1996"},{"key":"S1471068411000597_ref34","first-page":"649","volume-title":"Proceedings of the 7th International Semantic Web Conference (ISWC-08)","author":"Kr\u00f6tzsch","year":"2008"},{"key":"S1471068411000597_ref46","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88737-9_3"},{"key":"S1471068411000597_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48242-3_11"},{"key":"S1471068411000597_ref31","first-page":"199","volume-title":"Proceedings of the 17th International Joint Conference on Artificial Intelligence","author":"Horrocks","year":"2001"},{"key":"S1471068411000597_ref30","first-page":"723","volume-title":"Proccdings of the World Wide Web Conference (WWW)","author":"Horrocks","year":"2004"},{"key":"S1471068411000597_ref27","first-page":"103","article-title":"Conceptual logic programs","volume":"47","author":"Heymans","year":"2006","journal-title":"Annals of Mathematics and Artificial Intelligence (Special Issue on Answer Set Programming)"},{"key":"S1471068411000597_ref25","unstructured":"Heymans S. 2006. Decidable Open Answer Set Programming. PhD thesis, Theoretical Computer Science Lab (TINF), Department of Computer Science, Vrije Universiteit, Brussel."},{"key":"S1471068411000597_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05082-4_4"},{"key":"S1471068411000597_ref22","unstructured":"Grimm S. and Hitzler P. 2008. Defeasible inference with circumscriptive OWL ontologies. In Workshop on Advancing Reasoning on the Web: Scalability and Commonsense. No. 350 in CEUR-WS. Accessed 1 September 2011. URL: http:\/\/ceur-ws.org\/Vol-350\/paper6.pdf."},{"key":"S1471068411000597_ref18","first-page":"338","volume-title":"Proceedings of 6th Annual European Semantic Web Conference (ESWC 2009)","author":"Feier","year":"2009"},{"key":"S1471068411000597_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037172"},{"key":"S1471068411000597_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.04.002"},{"key":"S1471068411000597_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/505372.505373"},{"key":"S1471068411000597_ref9","first-page":"1","volume-title":"Proceedings of the 4th International Conference on Web Reasoning and Rule Systems (RR 2010)","author":"Cal\u00ec","year":"2010"},{"key":"S1471068411000597_ref26","first-page":"411","article-title":"Guarded hybrid knowledge bases","volume":"8","author":"Heymans","year":"2008","journal-title":"TPLP"},{"key":"S1471068411000597_ref29","doi-asserted-by":"publisher","DOI":"10.1145\/1380572.1380575"},{"key":"S1471068411000597_ref21","unstructured":"Grimm S. and Hitzler P. 2007 (September). Reasoning in Circumscriptive . Tech. Rep., FZI at University of Karlsruhe, Germany."},{"key":"S1471068411000597_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-008-9086-5"},{"key":"S1471068411000597_ref47","unstructured":"\u0160imkus M. and Eiter T. 2007. : Decidable non-monotonic disjunctive logic programs with function symbols. In Proceedings of the 14th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR 2007), Yerevan, Armenia. Lecture Notes in Computer Science. Springer, New York, 514\u2013530."},{"key":"S1471068411000597_ref50","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055090"},{"key":"S1471068411000597_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00883932"},{"key":"S1471068411000597_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514897"},{"key":"S1471068411000597_ref33","first-page":"80","volume-title":"Proceedings of the 18th European Conference on Artificial Intelligence (ECAI-08)","author":"Kr\u00f6tzsch","year":"2008"},{"key":"S1471068411000597_ref44","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2005.05.002"},{"key":"S1471068411000597_ref20","first-page":"1070","volume-title":"Proceedings of ICLP'88","author":"Gelfond","year":"1988"},{"key":"S1471068411000597_ref17","unstructured":"Feier C. and Heymans S. 2008. A sound and complete algorithm for simple conceptual logic programs. In Proceedings of ALPSWS 2008, Udine, Italy, December 9."},{"key":"S1471068411000597_ref8","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920912"},{"key":"S1471068411000597_ref5","unstructured":"Cal\u00ec A. , Gottlob G. and Kifer M. 2008. Taming the infinite chase: Query answering under expressive relational constraints. In Description Logics'08, vol. 353, F. Baader , C. Lutz and B. Motik , Eds. Accessed 1 September 2011. URL: http:\/\/ceur-ws.org\/Vol-353\/CaliGottlobKifer.pdf."},{"key":"S1471068411000597_ref19","first-page":"11","volume-title":"Proceedings of 22nd International Conference on Logic Programming (ICLP)","author":"Gebser","year":"2006"},{"key":"S1471068411000597_ref48","unstructured":"Smith M. , Welty C. and McGuinness D. 2004. OWL web ontology language guide [online]. Accessed 1 September 2011. URL: http:\/\/www.w3.org\/TR\/owl-guide\/"},{"key":"S1471068411000597_ref11","first-page":"274","volume-title":"Proceedings of IJCAI'2007","author":"Calvanese","year":"2007"},{"key":"S1471068411000597_ref43","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2005.05.001"},{"key":"S1471068411000597_ref24","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1145\/775152.775160","volume-title":"Proceedings of the World Wide Web Conference (WWW)","author":"Grosof","year":"2003"},{"key":"S1471068411000597_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2006.02.001"},{"key":"S1471068411000597_ref12","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008687430626"},{"key":"S1471068411000597_ref45","first-page":"68","volume-title":"Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR 2006)","author":"Rosati","year":"2006"},{"key":"S1471068411000597_ref1","volume-title":"The DL Handbook: Theory, Implementation, and Applications","author":"Baader","year":"2003"},{"key":"S1471068411000597_ref3","first-page":"400","volume-title":"Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR'06)","author":"Bonatti","year":"2006"},{"key":"S1471068411000597_ref4","first-page":"418","volume-title":"Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence","author":"Bonatti","year":"2008"},{"key":"S1471068411000597_ref6","first-page":"77","volume-title":"Proceedings of PODS-2009","author":"Cal\u00ec","year":"2009"},{"key":"S1471068411000597_ref10","first-page":"385","article-title":"Tractable reasoning and efficient query answering in description logics: The DL-Lite family","volume":"39","author":"Calvanese","year":"2007","journal-title":"Journal of Advanced Research"}],"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\/S1471068411000597","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,23]],"date-time":"2021-12-23T23:16:42Z","timestamp":1640301402000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068411000597\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,30]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["S1471068411000597"],"URL":"https:\/\/doi.org\/10.1017\/s1471068411000597","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12,30]]}}}