Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T10:32:46.390Z Has data issue: false hasContentIssue false

Module theorem for the general theory of stable models

Published online by Cambridge University Press:  05 September 2012

JOSEPH BABB
Affiliation:
School of Computing, Informatics, and Decision Systems Engineering, Arizona State University, Tempe, AZ, USA (e-mail: [email protected], [email protected])
JOOHYUNG LEE
Affiliation:
School of Computing, Informatics, and Decision Systems Engineering, Arizona State University, Tempe, AZ, USA (e-mail: [email protected], [email protected])

Abstract

The module theorem by Janhunen et al. demonstrates how to provide a modular structure in answer set programming, where each module has a well-defined input/output interface which can be used to establish the compositionality of answer sets. The theorem is useful in the analysis of answer set programs, and is a basis of incremental grounding and reactive answer set programming. We extend the module theorem to the general theory of stable models by Ferraris et al. The generalization applies to non-ground logic programs allowing useful constructs in answer set programming, such as choice rules, the count aggregate, and nested expressions. Our extension is based on relating the module theorem to the symmetric splitting theorem by Ferraris et al. Based on this result, we reformulate and extend the theory of incremental answer set computation to a more general class of programs.

Type
Regular Papers
Copyright
Copyright © Cambridge University Press 2012

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

Ferraris, P., Lee, J. and Lifschitz, V. 2007. A new perspective on stable models. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press, 372379.Google Scholar
Ferraris, P., Lee, J. and Lifschitz, V. 2011. Stable models and circumscription. Artificial Intelligence 175, 236263.CrossRefGoogle Scholar
Ferraris, P., Lee, J., Lifschitz, V. and Palla, R. 2009. Symmetric splitting in the general theory of stable models. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press, 797803.Google Scholar
Gebser, M., Grote, T., Kaminski, R. and Schaub, T. 2011. Reactive answer set programming. In Proceedings of International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR). Springer, 5466.CrossRefGoogle Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T. and Thiele, S. 2008. Engineering an incremental ASP solver. In Proceedings of the Twenty-fourth International Conference on Logic Programming (ICLP'08), Banda, M. Garcia de la and Pontelli, E., Eds. Lecture Notes in Computer Science, vol. 5366. Springer-Verlag, 190205.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of International Logic Programming Conference and Symposium, Kowalski, R. and Bowen, K., Eds. MIT Press, 10701080.Google Scholar
Janhunen, T., Oikarinen, E., Tompits, H. and Woltran, S. 2009. Modularity aspects of disjunctive stable models. Journal of Artificial Intelligence Research 35, 813857.CrossRefGoogle Scholar
Lee, J., Lifschitz, V. and Palla, R. 2008. A reductive semantics for counting and choice in answer set programming. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 472479.Google Scholar
Lee, J. and Meng, Y. 2012. Stable models of formulas with generalized quantifiers. In Proceedings of International Workshop on Nonmonotonic Reasoning (NMR). URL: http://peace.eas.asu.edu/joolee/papers/smgq-nmr.pdf.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 Inteligence Research (JAIR) 43, 571620.CrossRefGoogle Scholar
Lifschitz, V. 1994. Circumscription. In Handbook of Logic in AI and Logic Programming, Gabbay, D., Hogger, C. and Robinson, J., Eds. Vol. 3. Oxford University Press, 298352.Google Scholar
Oikarinen, E. and Janhunen, T. 2008. Achieving compositionality of the stable model semantics for smodels programs. TPLP 8, 5-6, 717761.Google Scholar
Supplementary material: PDF

BABB and LEE supplementary material

Appendix

Download BABB and LEE supplementary material(PDF)
PDF 292.7 KB