Abstract
Nonmonotonic description logic programs (dl-programs) are a well-known formalism for combining rules and ontologies, where rules interact with an underlying ontology via dl-atoms that allow queries to the ontology under a possible update of its assertional part. It is known that dl-atoms may be nonmonotonic and dl-programs without nonmonotonic dl-atoms have many desirable properties. In this paper, we show that it is possible to remove nonmonotonic dl-atoms from a dl-program while preserving its strong/weak answer set semantics. Though the translation is faithful, it relies on the knowledge about monotonicity of dl-atoms. We then thoroughly investigate the complexity of deciding whether a dl-atom is monotonic under the description logics DL-Lite\(_{\mathcal R}\), \({\mathcal{EL}}^{++}\), \({\mathcal{SHIF}}\) and \({\mathcal{SHOIN}}\), which is of independent interest for computing strong answer sets. We show that the problem is intractable in general, but tractable for dl-atoms with bounded queries in DL-Lite\(_{\mathcal R}\).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. Journal of Artifical Intelligence Research 36, 1–69 (2009)
Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: IJCAI 2005, pp. 364–369 (2005)
Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F.: The Description Logic Handbook, 2nd edn. Cambridge Univ. Press (2007)
Brewka, G., Eiter, T., Truszczynski, M.: Answer set programming at a glance. Communications of the ACM 54(12), 92–103 (2011)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. Journal of Automated Reasoning 39(3), 385–429 (2007)
de Bruijn, J., Bonnard, P., Citeau, H., Dehors, S., Heymans, S., Pührer, J., Eiter, T.: Combinations of rules and ontologies: State-of-the-art survey of issues. Technical Report Ontorule D3.1, Ontorule Project Consortium (2009), http://ontorule-project.eu/
de Bruijn, J., Eiter, T., Tompits, H.: Embedding approaches to combining rules and ontologies into autoepistemic logic. In: KR 2008, pp. 485–495. AAAI Press (2008)
de Bruijn, J., Pearce, D., Polleres, A., Valverde, A.: Quantified equilibrium logic and hybrid rules. In: Marchiori, M., Pan, J.Z., de Sainte Marie, C. (eds.) RR 2007. LNCS, vol. 4524, pp. 58–72. Springer, Heidelberg (2007)
Eiter, T., Fink, M., Krennwallner, T., Redl, C., Schüller, P.: Exploiting unfounded sets for hex-program evaluation. In: del Cerro, L.F., Herzig, A., Mengin, J. (eds.) JELIA 2012. LNCS, vol. 7519, pp. 160–175. Springer, Heidelberg (2012)
Eiter, T., Fink, M., Stepanova, D.: Semantic independence in DL-programs. In: Krötzsch, M., Straccia, U. (eds.) RR 2012. LNCS, vol. 7497, pp. 58–74. Springer, Heidelberg (2012)
Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Combining answer set programming with description logics for the semantic web. Artificial Intelligence 172(12-13), 1495–1539 (2008)
Eiter, T., Ianni, G., Schindlauer, R., Tompits, H.: A uniform integration of higher-order reasoning and external evaluations in answer-set programming. In: IJCAI 2005, pp. 90–96. Professional Book Center (2005)
Eiter, T., Lukasiewicz, T., Ianni, G., Schindlauer, R.: Well-founded semantics for description logic programs in the semantic web. ACM TOCL 12(2), 11:1–11:41 (2011)
Fink, M., Pearce, D.: A logical semantics for description logic programs. In: Janhunen, T., Niemelä, I. (eds.) JELIA 2010. LNCS, vol. 6341, pp. 156–168. Springer, Heidelberg (2010)
Horrocks, I., Patel-Schneider, P.F.: Reducing OWL entailment to description logic satisfiability. In: Fensel, D., Sycara, K., Mylopoulos, J. (eds.) ISWC 2003. LNCS, vol. 2870, pp. 17–29. Springer, Heidelberg (2003)
Lee, J., Palla, R.: Integrating rules and ontologies in the first-order stable model semantics (Preliminary report). In: Delgrande, J.P., Faber, W. (eds.) LPNMR 2011. LNCS, vol. 6645, pp. 248–253. Springer, Heidelberg (2011)
Lifschitz, V., Tang, L.R., Turner, H.: Nested expressions in logic programs. Annals of Mathematics and Artificial Intelligence 25(3-4), 369–389 (1999)
Motik, B., Rosati, R.: Reconciling description logics and rules. Journal of the ACM 57(5), 1–62 (2010)
Pratt-Hartmann, I.: Complexity of the two-variable fragment with counting quantifiers. Journal of Logic, Language and Information 14(3), 369–395 (2005)
Reiter, R.: A logic for default reasoning. Artificial Intelligence 13(1-2), 81–132 (1980)
Rosati, R.: On the decidability and complexity of integrating ontologies and rules. Journal of Web Semantics 3(1), 61–73 (2005)
Rosati, R.: DL+log: Tight integration of description logics and disjunctive datalog. In: KR 2006, pp. 68–78. AAAI Press (2006)
Shen, Y.-D.: Well-supported semantics for description logic programs. In: IJCAI 2011, pp. 1081–1086. IJCAI/AAAI (2011)
Tobies, S.: Complexity Results and Practical Algorithms for Logics in Knowledge Representation. PhD thesis, RWTH Aachen, Germany (2001)
Wang, Y., You, J.-H., Yuan, L.Y., Shen, Y.-D., Zhang, M.: The loop formula based semantics of description logic programs. TCS 415, 60–85 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, Y., Eiter, T., You, JH., Yuan, L., Shen, YD. (2013). Eliminating Nonmonotonic DL-Atoms in Description Logic Programs. In: Faber, W., Lembo, D. (eds) Web Reasoning and Rule Systems. RR 2013. Lecture Notes in Computer Science, vol 7994. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39666-3_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-39666-3_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39665-6
Online ISBN: 978-3-642-39666-3
eBook Packages: Computer ScienceComputer Science (R0)