Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-17T22:23:08.639Z Has data issue: false hasContentIssue false
  • English
  • Français

Reasoning with Forest Logic Programs and f-hybrid knowledge bases*†

Published online by Cambridge University Press:  30 December 2011

CRISTINA FEIER  and
STIJN HEYMANS
CRISTINA FEIER
Affiliation:
Knowledge-Based Systems Group, Institute of Information Systems, Vienna University of Technology, Favoritenstrasse 9-11, A-1040 Vienna, Austria (e-mail: [email protected], [email protected])
STIJN HEYMANS
Affiliation:
Knowledge-Based Systems Group, Institute of Information Systems, Vienna University of Technology, Favoritenstrasse 9-11, A-1040 Vienna, Austria (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 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.

Keywords

Forest Logic Programsfinite model propertyf-hybrid knowledge basesopen answer setsintegration of rules and ontologies
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 13 , Issue 3 , May 2013 , pp. 395 - 463
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

A preliminary version of this paper appeared in the Proceedings of the European Semantic Web Conference 20009 (ESWC2009). We extended that paper with detailed examples, a more detailed description of the algorithm and the fragment of f-hybrid knowledge bases, a detailed characterisation of simple FoLPs, as well as with proofs for all theorems (Feier and Heymans 2009).

†

This work is partially supported by the Austrian Science Fund (FWF) under the projects P20305 and P20840, and by the European Commission under the project OntoRule (IST-2009-231875).

References

Baader, F., Calvanese, D., McGuinness, D. L., Nardi, D. and Patel-Schneider, P. F., (Eds). 2003. The DL Handbook: Theory, Implementation, and Applications. Cambridge University Press, Cambridge, UK.Google Scholar
Baader, F. and Hollunder, B. 1995. Embedding defaults into terminological representation systems. Journal of Automated Reasoning 14, 2, 149–180.Google Scholar
Bonatti, P., Lutz, C. and Wolter, F. 2006. Expressive non-monotonic description logics based on circumscription. In Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR'06), Lake District, UK, June 2–5. AAAI Press, Menlo Park, CA, 400–410.Google Scholar
Bonatti, P., Pontelli, E. and Son, T. C. 2008. Credulous resolution for answer set programming. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, Chicago, IL, USA, July 13–17. AAAI Press, Menlo Park, CA, 418–423.Google Scholar
Calì, A., Gottlob, G. and Kifer, M. 2008. Taming the infinite chase: Query answering under expressive relational constraints. In Description Logics'08, vol. 353, Baader, F., Lutz, C. and Motik, B., Eds. Accessed 1 September 2011. URL: http://ceur-ws.org/Vol-353/CaliGottlobKifer.pdf.Google Scholar
Calì, A., Gottlob, G. and Lukasiewicz, T. 2009a. A general datalog-based framework for tractable query answering over ontologies. In Proceedings of PODS-2009. ACM Press, New York, 77–86.Google Scholar
Calì, A., Gottlob, G. and Lukasiewicz, T. 2009b. Datalog: A unified approach to ontologies and integrity constraints. In Proceedings of the International Conference on Database Theory (ICDT '09), St. Petersburg, Russia, March 23–25. ACM International Conference Proceeding Series, ACM Press, New York, 14–30.CrossRefGoogle Scholar
Calì, A., Gottlob, G. and Pieris, A. 2010a. Advanced processing for ontological queries. Proceedings of the VLDB Endowment 3, 1, 554–565.Google Scholar
Calì, A., Gottlob, G. and Pieris, A. 2010b. Query answering under non-guarded rules in datalog. In Proceedings of the 4th International Conference on Web Reasoning and Rule Systems (RR 2010), Bressanone/Brixen, Italy, September 2010. Lecture Notes in Computer Science, vol. 6333. Springer, Berlin, 1–17.Google Scholar
Calvanese, D., de Giacomo, G., Lembo, D., Lenzerini, M. and Rosati, R. 2007a. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. Journal of Advanced Research 39, 3, 385–429.Google Scholar
Calvanese, D., DEGiacomo, G. Giacomo, G., Lembo, D., Lenzerini, M. and Rosati, R. 2007b. Eql-Lite: Effective first-order query processing in description logics. In Proceedings of IJCAI'2007, Hyderabad, India, January 6–12. Springer, Berlin, 274–279.Google Scholar
Donini, F., Lenzerini, M., Nardi, D. and Schaerf, A. 1998. AL-log: Integrating datalog and description logics. Journal of Intelligent and Cooperative Information Systems 10, 227–252.Google Scholar
Donini, F. M., Nardia, D. and Rosati, R. 2002. Description logics of minimal knowledge and negation as failure. ACM Transactions on Computational Logic 3, 2, 177–225.CrossRefGoogle Scholar
Eiter, T., Faber, W., Fink, M. and Woltran, S. 2007. Complexity results for answer set programming with bounded predicate arities and implications source. Annals of Mathematics and Artificial Intelligence 51, 1–2, 123–165.CrossRefGoogle Scholar
Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R. and Tompits, H. 2008. Combining answer set programming with description logics for the semantic web. Artificial Intelligence 172, 12–13, 1495–1539.CrossRefGoogle Scholar
Fages, F. 1991. A new fix point semantics for generalized logic programs compared with the well-founded and the stable model semantics. New Generation Computing 9, 4, 425–444.Google Scholar
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.Google Scholar
Feier, C. and Heymans, S. 2009. Hybrid reasoning with forest logic programs. In Proceedings of 6th Annual European Semantic Web Conference (ESWC 2009), vol. 5554. Springer, New York, 338–352.Google Scholar
Gebser, M. and Schaub, T. 2006. Tableau calculi for answer set programming. In Proceedings of 22nd International Conference on Logic Programming (ICLP). Lecture Notes in Computer Science, vol. 4079. Springer, New York, 11–25.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of ICLP'88, Seattle, Washington, USA, August 15–19. MIT Press, Cambridge, MA, USA, 1070–1080.Google Scholar
Grimm, S. and Hitzler, P. 2007 (September). Reasoning in Circumscriptive . Tech. Rep., FZI at University of Karlsruhe, Germany.Google Scholar
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.Google Scholar
Grimm, S. and Hitzler, P. 2009. A preferential tableaux calculus for circumscriptive ALCO. In Proceedings of the 3rd International Conference on Web Reasoning and Rule Systems (RR 2009), Polleres, A. and Swift, T., Eds., vol. 5837. Springer, New York, 40–54.Google Scholar
Grosof, B. N., Horrocks, I., Volz, R. and Decker, S. 2003. Description logic programs: Combining logic programs with description logic. In Proceedings of the World Wide Web Conference (WWW), Budapest, Hungary, May 20–24. ACM, New York, 48–57.CrossRefGoogle Scholar
Heymans, S. 2006. Decidable Open Answer Set Programming. PhD thesis, Theoretical Computer Science Lab (TINF), Department of Computer Science, Vrije Universiteit, Brussel.Google Scholar
Heymans, S., de Bruijn, J., Predoiu, L., Feier, C. and VanNieuwenborgh, D. Nieuwenborgh, D. 2008. Guarded hybrid knowledge bases. TPLP 8, 3, 411–429.Google Scholar
Heymans, S., Van Nieuwenborgh, D. and Vermeir, D. 2006. Conceptual logic programs. Annals of Mathematics and Artificial Intelligence (Special Issue on Answer Set Programming) 47, 1–2, 103–137.Google Scholar
Heymans, S., Van Nieuwenborgh, D. and Vermeir, D. 2007. Open answer set programming for the semantic web. Journal of Applied Logic 5, 1, 144–169.Google Scholar
Heymans, S., Van Nieuwenborgh, D. and Vermeir, D. 2008. Open answer set programming with guarded programs. ACM Transactions on Computational Logic 9, 4 (August), 1–53.Google Scholar
Horrocks, I. and Patel-Schneider, P. F. 2004. A proposal for an OWL rules language. In Proccdings of the World Wide Web Conference (WWW), New York, USA. ACM, New York, 723–731.Google Scholar
Horrocks, I. and Sattler, U. 2001. Ontology reasoning in the SHOQ(D) description logic. In Proceedings of the 17th International Joint Conference on Artificial Intelligence, Seattle, Washington, USA. Morgan Kaufmann, San Fransisco, CA, 199–204.Google Scholar
Horrocks, I., Sattler, U. and Tobies, S. 1999. Practical reasoning for expressive description logics. In Proceedings of the 6th International Conference on Logic for Programming and Automated Reasoning (LPAR'99), Lecture Notes in Computer Science, vol. 1705. Springer, New York, 161–180.Google Scholar
Krötzsch, M., Rudolph, S. and Hitzler, P. 2008a. Description logic rules. In Proceedings of the 18th European Conference on Artificial Intelligence (ECAI-08). IOS Press, Lansdale PA, 80–84.Google Scholar
Krötzsch, M., Rudolph, S. and Hitzler, P. 2008b. ELP: Tractable rules for OWL 2. In Proceedings of the 7th International Semantic Web Conference (ISWC-08), Karlsruhe, Germany. Springer, Berlin, 649–664.Google Scholar
Levy, A. Y. and Rousset, M. 1996. CARIN: A representation language combining horn rules and description logics. In Proceedings of ECAI'96, Budapest, Hungary, August 13. John Wiley, Chichester, UK, 323–327.Google Scholar
Lierler, Y. 2008. Abstract answer set solvers. In Proceedings of the 26th International Conference on Logic Programming (ICLP), Udine, Italy, December 9–13. Springer, New York, 377–391.Google Scholar
Lin, F. and You, J. 2002. Abduction in logic programming: A new definition and an abductive procedure based on rewriting. Artificial Intelligence 140, 175–205.CrossRefGoogle Scholar
Lukasiewicz, T. 2004. A novel combination of answer set programming with description logics for the semantic web. In Proceedings of KR-2004. AAAI Press, Palo Alto, CA, 141–151.Google Scholar
Minsky, M. 1985. A framework for representing knowledge. In Readings in Knowledge Representation, Brachman, R. J. and Levesque, H. J., Eds. Kaufmann, Los Altos, CA, 245–262.Google Scholar
Motik, B., Horrocks, I., Rosati, R. and Sattler, U. 2006. Can OWL and logic programming live together happily ever after? In Proceedings of the International Semantic Web Conference (ISWC). Lecture Notes in Computer Science, vol. 4273. Springer, New York, 501–514.Google Scholar
Motik, B. and Rosati, R. 2006. Closing Semantic Web Ontologies. Tech. Rep., University of Manchester, UK.Google Scholar
Motik, B. and Rosati, R. 2010. Reconciling description logics and rules. Journal of the ACM 57, 5, 30:1–30:62.CrossRefGoogle Scholar
Motik, B., Sattler, U. and Studer, R. 2005. Query answering for OWL-DL with rules. Journal of Web Semantics 3, 1, 41–60.Google Scholar
Rosati, R. 2005. On the decidability and complexity of integrating ontologies and rules. Web Semantics 3, 1, 41–60.CrossRefGoogle Scholar
Rosati, R. 2006. DL+log: Tight integration of description logics and disjunctive datalog. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR 2006), Lake District, UK, June 2–5. AAAI Press, Palo Alto, CA, 68–78.Google Scholar
Rosati, R. 2008. On combining description logic ontologies and nonrecursive datalog rules. In Proceedings of the 2nd International Conference on Web Reasoning and Rule Systems (RR 2008), Karlsruhe, Germany. Springer, New York, 13–27.CrossRefGoogle Scholar
Šimkus, 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–530.Google Scholar
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/Google Scholar
Tobies, S. 2001. Complexity Results and Practical Algorithms for Logics in Knowledge Representation. PhD thesis, RWTH-Aachen, Aachen, Germany.Google Scholar
Vardi, M. Y. 1998. Reasoning about the past with two-way automata. In Proceedings of the 25th International Colloquium on Automata, Languages and Programming. Springer, New York, 628–641.Google Scholar