Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T05:55:34.675Z Has data issue: false hasContentIssue false
  • English
  • Français

Loop formulas for description logic programs

Published online by Cambridge University Press:  09 July 2010

YISONG WANG ,
JIA-HUAI YOU ,
LI YAN YUAN  and
YI-DONG SHEN
YISONG WANG
Affiliation:
Department of Computer Science, Guizhou University, Guiyang, China Department of Computing Science, University of Alberta, Canada
JIA-HUAI YOU
Affiliation:
Department of Computing Science, University of Alberta, Canada
LI YAN YUAN
Affiliation:
Department of Computing Science, University of Alberta, Canada
YI-DONG SHEN
Affiliation:
State Key Laboratory of Computer Science Institute of Software, Chinese Academy of Sciences, China
Get access Rights & Permissions [Opens in a new window]

Abstract

Description Logic Programs (dl-programs) proposed by Eiter et al. constitute an elegant yet powerful formalism for the integration of answer set programming with description logics, for the Semantic Web. In this paper, we generalize the notions of completion and loop formulas of logic programs to description logic programs and show that the answer sets of a dl-program can be precisely captured by the models of its completion and loop formulas. Furthermore, we propose a new, alternative semantics for dl-programs, called the canonical answer set semantics, which is defined by the models of completion that satisfy what are called canonical loop formulas. A desirable property of canonical answer sets is that they are free of circular justifications. Some properties of canonical answer sets are also explored.

Keywords

semantic webdescription logic programsanswer setsloop formulas
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 10 , Special Issue 4-6: 26th International Conference on Logic Programming , July 2010 , pp. 531 - 545
Copyright
Copyright © Cambridge University Press 2010

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

References

Baader, F., Calvanese, D., McGuinness, D. L., Nardi, D., and Patel-Schneider, P. F. 2007. The Description Logic Handbook: Theory, Implementation, and Applications, 2nd ed.Cambridge University Press, New York.CrossRefGoogle Scholar
Berners-Lee, T., Hendler, J., and Lassila, O. 2001. The semantic web. Scientific American Magazine 284, 5, 34–43.CrossRefGoogle Scholar
Brewka, G. and Eiter, T. 2007. Equilibria in heterogeneous nonmonotonic multi-context systems. In Proceedings of AAAI 2007. AAAI Press, Vancouver, BC, Canada, 385–390.Google Scholar
Bruijn, J., Eiter, T., Polleres, A., and Tompits, H. 2007. Embedding non-ground logic programs into autoepistemic logic for knowledge-base combination. In Proceedings of 20th International Conference on Artificial Intelligence. Morgan Kaufman, 304–309.Google Scholar
Calimeri, F., Faber, W., Leone, N., and Perri, S. 2005. Declarative and computational properties of logic programs with aggregates. In Proceedings of IJCAI 2005. Edinburgh, Scotland, UK, 406–411.Google Scholar
Chen, Y., Lin, F., Wang, Y., and Zhang, M. 2006. First-order loop formulas for normal logic programs. In Proceedings of KR 2006. AAAI Press, Lake District, UK, 298–307.Google Scholar
de Bruijn, J., Pearce, D., Polleres, A., and Valverde, A. 2007. Quantified equilibrium logic and hybrid rules. In Proceedings of Web Reasoning and Rule Systems, First International Conference. Lecture Notes in Computer Science, vol. 4524. Springer, Innsbruck, Austria.Google 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
Horrocks, I. and Patel-Schneider, P. F. 2004. A proposal for an OWL rules language. In Proceedings of WWW 2004. ACM, New York, 723–731.Google Scholar
Lee, J. and Meng, Y. 2008. On loop formulas with variables. In Proceedings of KR 2008. AAAI Press, Sydney, 444–453.Google Scholar
Lin, F. and Zhao, Y. 2004. ASSAT: Computing answer sets of a logic program by SAT solvers. Artificial Intelligence 157, 1–2, 115–137.CrossRefGoogle Scholar
Liu, G. and You, J.-H. 2008. Lparse programs revisited: Semantics and representation of aggregates. In Proceedings of ICLP 2008. Lecture Notes in Computer Science, vol. 5366. Springer, Udine, Italy, 347–361.Google Scholar
Marek, V. W. and Truszczynski, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: A 25-Year Perspective, Apt, K., Marek, V., Truszczynski, M., and Warren, D., Eds. Springer, Berlin, 375–398.CrossRefGoogle Scholar
Motik, B. and Rosati, R. 2010. Reconciling description logics and rules. Journal of the ACM 36, 165–228.Google Scholar
Niemelä, I. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 3-4, 241–273.CrossRefGoogle Scholar
Rosati, R. 2005. On the decidability and complexity of integrating ontologies and rules. Journal of Web Semantics 3, 1, 61–73.CrossRefGoogle Scholar
Rosati, R. 2006. DL+log: Tight integration of description logics and disjunctive datalog. In Proceedings of KR 2006. AAAI Press, Lake District, UK, 68–78.Google Scholar
Van Gelder, A., Ross, K. A., and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. Journal of the ACM 38, 3, 620–650.CrossRefGoogle Scholar
W3C OWL Working Group. 2009. OWL 2 Web Ontology Language: Document Overview. W3C Recommendation, Available at http://www.w3.org/TR/owl2-overview/.Google Scholar