Abstract
In previous work, towards the integration of rules and ontologies in the Semantic Web, we have proposed a combination of logic programming under the answer set semantics with the description logics \({\cal SHIF}({\mathbf{D}})\) and \({\cal SHOIN}({\mathbf{D}})\), which underly the Web ontology languages OWL Lite and OWL DL, respectively. More precisely, we have introduced description logic programs (or dl-programs), which consist of a description logic knowledge base L and a finite set of description logic rules P, and we have defined their answer set semantics. In this paper, we continue this line of research. Here, as a central contribution, we present the well-founded semantics for dl-programs, and we analyze its semantic properties. In particular, we show that it generalizes the well-founded semantics for ordinary normal programs. Furthermore, we show that in the general case, the well-founded semantics of dl-programs is a partial model that approximates the answer set semantics, whereas in the positive and the stratified case, it is a total model that coincides with the answer set semantics. Finally, we also provide complexity results for dl-programs under the well-founded semantics.
This work was partially supported by the Austrian Science Fund under grants Z29-N04 and P17212-N04, by the European Commission through the IST REWERSE Network of Excellence and the Marie Curie Individual Fellowship HPMF-CT-2001-001286 (disclaimer: The authors are solely responsible for information communicated and the European Commission is not responsible for any views or results expressed), and by the German Research Foundation through a Heisenberg Fellowship. We thank Ulrike Sattler for providing valuable information on complexity-related issues about OWL-DL related description logics.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alsaç, G., Baral, C.: Reasoning in description logics using declarative logic programming. Tech. report, Computer Science and Engineering Dept., Arizona State University (2001)
Antoniou, G.: Nonmonotonic rule systems on top of ontology layers. In: Horrocks, I., Hendler, J. (eds.) ISWC 2002. LNCS, vol. 2342, pp. 394–398. Springer, Heidelberg (2002)
Antoniou, G., Wagner, G.: Rules and defeasible reasoning on the Semantic Web. In: Schröder, M., Wagner, G. (eds.) RuleML 2003. LNCS, vol. 2876, pp. 111–120. Springer, Heidelberg (2003)
Baader, F., Hollunder, B.: Embedding defaults into terminological representation systems. J. Automated Reasoning 14, 149–180 (1995)
Baral, C., Subrahmanian, V.S.: Dualities between alternative semantics for logic programming and nonmonotonic reasoning. J. Automated Reasoning 10(3), 399–420 (1993)
Berners-Lee, T.: Weaving the Web. Harper, San Francisco (1999)
Berners-Lee, T., Hendler, J., Lassila, O.: The Semantic Web. Scientific American 284(5), 34–43 (2001)
Boley, H., Tabet, S., Wagner, G.: Design rationale for RuleML: A markup language for Semantic Web rules. In: Proc. SWWS 2001, pp. 381–401 (2001)
Brewka, G.: On the relationship between defeasible logic and well-founded semantics. In: Eiter, T., Faber, W., Truszczyński, M. (eds.) LPNMR 2001. LNCS (LNAI), vol. 2173, pp. 121–132. Springer, Heidelberg (2001)
Damásio, C.V.: The W4 Project (2002), http://centria.di.fct.unl.pt/~cd/projectos/w4/index.htm
Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and expressive power of logic programming. ACM Computing Surveys 33(3), 374–425 (2001)
Donini, F.M., Lenzerini, M., Nardi, D., Schaerf, A.: \({\mathcal AL}\)-log: Integrating datalog and description logics. Journal of Intelligent Information Systems (JIIS) 10(3), 227–252 (1998)
Eiter, T., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Combining answer set programming with description logics for the Semantic Web. In: Proc. KR 2004, pp. 141–151 (2004); Preliminary Report RR-1843-03-13, Institut für Informationssysteme, TU Wien (2003)
Fensel, D., Wahlster, W., Lieberman, H., Hendler, J. (eds.): Spinning the Semantic Web: Bringing the World Wide Web to Its Full Potential. MIT Press, Cambridge (2002)
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and deductive databases. New Generation Computing 17, 365–387 (1991)
Grosof, B.N.: Courteous logic programs: Prioritized conflict handling for rules. IBM Research Report RC 20836, IBM Research Division, T.J. Watson Research (1997)
Grosof, B.N., Horrocks, I., Volz, R., Decker, S.: Description logic programs: Combining logic programs with description logics. In: Proc. WWW 2003, pp. 48–57 (2003)
Haarslev, V., Möller, R.: RACER system description. In: Goré, R.P., Leitsch, A., Nipkow, T. (eds.) IJCAR 2001. LNCS (LNAI), vol. 2083, pp. 701–705. Springer, Heidelberg (2001)
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)
Horrocks, I., Patel-Schneider, P.F.: A proposal for an OWL Rules Language. In: Proc. WWW 2004, pp. 723–731 (2004)
Horrocks, I., Patel-Schneider, P.F., van Harmelen, F.: From \({\mathcal SHIQ}\) and RDF to OWL: The making of a web ontology language. Journal of Web Semantics 1(1), 7–26 (2003)
Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for expressive description logics. In: Ganzinger, H., McAllester, D., Voronkov, A. (eds.) LPAR 1999. LNCS, vol. 1705, pp. 161–180. Springer, Heidelberg (1999)
Hufstadt, U., Motik, B., Sattler, U.: Reasoning for description logics around \({\mathcal SHIQ}\) in a resolution framework. Technical Report 3-8-04/04, FZI Karlsruhe (2004)
Levy, A.Y., Rousset, M.-C.: Combining Horn rules and description logics in CARIN. Artif. Intell. 104(1-2), 165–209 (1998)
Maher, M.J., Governatori, G.: A semantic decomposition of defeasible logics. In: Proc. AAAI/IAAI 1999, pp. 299–305 (1999)
May, W., Ludäscher, B., Lausen, G.: Well-founded semantics for deductive object-oriented database languages. In: Bry, F., Ramakrishnan, R., Ramamohanarao, K. (eds.) DOOD 1997. LNCS, vol. 1341, pp. 320–336. Springer, Heidelberg (1997)
Niemelä, I., Simons, P., Syrjänen, T.: Smodels: A system for answer set programming. In: Proc. NMR 2000 (2000)
Rao, P., Sagonas, K., Swift, T., Warren, D.S., Freire, J.: XSB: A system for efficiently computing WFS. In: Fuhrbach, U., Dix, J., Nerode, A. (eds.) LPNMR 1997. LNCS, vol. 1265, pp. 430–440. Springer, Heidelberg (1997)
Rosati, R.: Towards expressive KR systems integrating datalog and description logics: Preliminary report. In: Proc. DL 1999, pp. 160–164 (1999)
Swift, T.: Deduction in ontologies via ASP. In: Lifschitz, V., Niemelä, I. (eds.) LPNMR 2004. LNCS (LNAI), vol. 2923, pp. 275–288. Springer, Heidelberg (2003)
Tobies, S.: Complexity Results and Practical Algorithms for Logics in Knowledge Representation. PhD thesis, RWTH Aachen, Germany (2001)
Van Belleghem, K., Denecker, M., De Schreye, D.: A strong correspondence between description logics and open logic programming. In: Proc. ICLP 1997, pp. 346–360 (1997)
Van Gelder, A.: The alternating fixpoint of logic programs with negation. In: Proc. PODS 1989, pp. 1–10 (1989)
Van Gelder, A., Ross, K.A., Schlipf, J.S.: The well-founded semantics for general logic programs. Journal of the ACM 38(3), 620–650 (1991)
W3C. OWL web ontology language overview, W3C Recommendation (February 10, 2004), Available at http://www.w3.org/TR/2004/REC-owl-features-20040210/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Eiter, T., Lukasiewicz, T., Schindlauer, R., Tompits, H. (2004). Well-Founded Semantics for Description Logic Programs in the Semantic Web. In: Antoniou, G., Boley, H. (eds) Rules and Rule Markup Languages for the Semantic Web. RuleML 2004. Lecture Notes in Computer Science, vol 3323. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30504-0_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-30504-0_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23842-3
Online ISBN: 978-3-540-30504-0
eBook Packages: Springer Book Archive