Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-23T12:08:30.406Z Has data issue: false hasContentIssue false
  • English
  • Français

Disjunctive logic programs with existential quantification in rule heads

Published online by Cambridge University Press:  25 September 2013

JIA-HUAI YOU ,
HENG ZHANG  and
YAN ZHANG
JIA-HUAI YOU
Affiliation:
University of Alberta, Edmonton T6G 2E8, Canada
HENG ZHANG
Affiliation:
University of Western Sydney, Penrith, NSW 2751, Australia
YAN ZHANG
Affiliation:
University of Western Sydney, Penrith, NSW 2751, Australia
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider disjunctive logic programs without function symbols but with existential quantification in rule heads, under the semantics of general stable models. There are at least two interesting prospects in these programs. The first is that a program can be made more succinct by using existential variables, and the second is on the potential in representing defeasible ontological knowledge by these logic programs. This paper studies some of the properties of these programs. First, we show a simple yet intuitive definition of stable models for these programs that does not resort to second-order logic. Second, the stable models of these programs can be characterized by an extension of progression for disjunctive programs, which provides a native characterization of justification for stable models. We then study the decidability issue. While the stable model existence problem for safe disjunctive programs is decidable, with existential quantification allowed in rule heads the problem becomes undecidable. We identify an interesting decidable fragment by exploring a new notion of stratification over existential quantification.

Keywords

disjunctive logic programsgeneral stable modelsexistential quantification
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 13 , Special Issue 4-5: 29th International Conference on Logic Programming , July 2013 , pp. 563 - 578
Copyright
Copyright © 2013 [JIA-HUAI YOU, HENG ZHANG and YAN ZHANG] 

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

Alviano, M., Faber, W., Leone, N. and Manna, M. 2012. Disjunctive datalog with existential quantifiers: Semantics, decidability, and complexity issues. Theory and Practice of Logic Programming 12, 4–5, 701–718.CrossRefGoogle Scholar
Bartholomew, M. and Lee, J. 2010. A decidable class of groundable formulas in the general theory of stable models. In Proc. KR-2010.Google Scholar
Berger, R. 1966. The undecidability of the domino problem. Memoirs of the American Mathematical Society 66, 1, 1–72.Google Scholar
Bonatti, P. A., Faella, M. and Sauro, L. 2011. Defeasible inclusions in low-complexity DLs. Journal of Artificial Intelligence Research 42, 719–764.Google Scholar
Cabalar, P., Pearce, D. and Valverde, A. 2009. A revised concept of safety for general answer set programs. In Proc. LPNMR, 58–70.Google Scholar
Cadoli, M., Eiter, T. and Gottlob, G. 1997. Default logic as a query language. IEEE Transactions on Knowledge and Data Engineering 9, 3, 448–463.CrossRefGoogle Scholar
Calì, A., Gottlob, G. and Kifer, M. 2008. Taming the infinite chase: Query answering under expressive relational constraints. In KR, 70–80.Google Scholar
Calì, A., Gottlob, G. and Lukasiewicz, T. 2009. A general datalog-based framework for tractable query answering over ontologies. In Proc. PODS, 77–86.Google Scholar
Calì, A., Gottlob, G. and Pieris, A. 2012. Towards more expressive ontology languages: The query answering problem. Artificial Intelligence 193, 87–128.CrossRefGoogle Scholar
Casini, G. and Straccia, U. 2011. Defeasible inheritance-based description logics. In Proc. IJCAI-11, 813–818.Google Scholar
Eiter, T., Gottlob, G. and Mannila, H. 1997. Disjunctive datalog. ACM Transactions Database System 22, 3, 364–418.CrossRefGoogle Scholar
Fages, F. 1994. Consistency of clark's completion and existence of stable models. Journal of Methods of Logic in Computer Science 1, 51–60.Google Scholar
Fagin, R., Kolaitis, P. G., Miller, R. J. and Popa, L. 2005. Data exchange: Semantics and query answering. Theoretical Computer Science 336, 1, 89–124.CrossRefGoogle Scholar
Ferraris, P., Lee, J. and Lifschitz, V. 2011. Stable models and circumscription. Artificial Intelligence 175, 1, 236–263.CrossRefGoogle Scholar
Ferraris, P., Lee, J., Lifschitz, V. and Palla, R. 2009. Symmetric splitting in the general theory of stable models. In IJCAI-09, 797–803.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. ICLP'88, 1070–1080.Google Scholar
Gottlob, G., Hernich, A., Kupke, C. and Lukasiewicz, T. 2012. Equality-friendly well-founded semantics and applications to description logics. In Proc. AAAI-12.Google Scholar
Gurevich, Y. and Koryakov, I. 1972. Remarks on Berger's paper on the domino problem. Siberian Mathematical Journal 13, 319–321.CrossRefGoogle Scholar
Lee, J., Lifschitz, V. and Palla, R. 2008. Safe formulas in the general theory of stable models (preliminary report). In Proc. ICLP, 672–676.Google Scholar
Lee, J. and Meng, Y. 2011. First-order stable model semantics and first-order loop formulas. Journal of Artificial Intelligence Research (JAIR) 42, 125–180.Google Scholar
Lee, J. and Palla, R. 2012. Reformulating the situation calculus and the event calculus in the general theory of stable models and in answer set programming. Journal of Artificial Intelligence Research (JAIR) 43, 571–620.CrossRefGoogle Scholar
Leone, N., Manna, M., Terracina, G. and Veltri, P. 2012. Efficiently computable datalog; programs. In KR.Google Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7, 3, 499–562.CrossRefGoogle Scholar
Lin, F. and Zhou, Y. 2011. From answer set logic programming to circumscription via logic of GK. Artificial Intelligence 175, 1, 264–277.CrossRefGoogle Scholar
Motik, B. and Rosati, R. 2010. Reconciling description logics and rules. Journal of the ACM 57, 5, 1–62.CrossRefGoogle 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
Nieuwenhuis, R., Oliveras, A. and Tinelli, C. 2006. Solving SAT and SAT modulo theories: From an abstract davis–putnam–logemann–loveland procedure to DPLL(T). Journal of ACM 53, 6, 937–977.CrossRefGoogle Scholar
You, J.-H., Shen, Y.-D. and Wang, K. 2012. Well-supported semantics for logic programs with generalized rules. In Correct Reasoning: Essays on Logic-Based AI in Honor of Vladimir Lifschitz, LNCS 7265, 576–591.Google Scholar
Zhang, H. and Ying, M. 2010. Decidable fragments of first-order language under stable model semantics and circumscription. In Proc. AAAI-10.CrossRefGoogle Scholar
Zhang, H., Zhang, Y., Ying, M. and Zhou, Y. 2011. Translating first-order theories into logic programs. In Proc. IJCAI-11, 1126–1131.Google Scholar
Zhou, Y. and Zhang, Y. 2011. Progression semantics for disjunctive logic programs. In Proc. AAAI-11, 286–291.Google Scholar
Supplementary material: PDF

You et al. supplementary material

Appendix

Download You et al. supplementary material(PDF)
PDF 194.3 KB