No CrossRef data available.
Article contents
A Constructive semantic characterization of aggregates in answer set programming
Published online by Cambridge University Press: 01 May 2007
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
This technical note describes a monotone and continuous fixpoint operator to compute the answer sets of programs with aggregates. The fixpoint operator relies on the notion of aggregate solution. Under certain conditions, this operator behaves identically to the three-valued immediate consequence operator ΦaggrP for aggregate programs, independently proposed in Pelov (2004) and Pelov et al. (2004). This operator allows us to closely tie the computational complexity of the answer set checking and answer sets existence problems to the cost of checking a solution of the aggregates in the program. Finally, we relate the semantics described by the operator to other proposals for logic programming with aggregates.
Information
- Type
- Technical Note
- Information
- Copyright
- Copyright © Cambridge University Press 2007
References
Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. 2001. Introduction to Algorithms, 2nd Edition. MIT Press, Cambridge, MA.Google Scholar
Dovier, A., Pontelli, E., and Rossi, G. 2001. Constructive negation and constraint logic programming with sets. New Generation Comput. 19, 3, 209–256.CrossRefGoogle Scholar
Dovier, A., Pontelli, E., and Rossi, G. 2003. Intensional Sets in CLP. In International Conference on Logic Programming, Springer, 284–299.Google Scholar
Elkabani, I., Pontelli, E., and Son, T. C. 2004. Smodels with CLP and its Applications: a Simple and Effective Approach to Aggregates in ASP. In International Conference on Logic Programming, Springer, 73–89.Google Scholar
Faber, W., Leone, N., and Pfeifer, G. 2004. Recursive Aggregates in Disjunctive Logic Programs: Semantics and Complexity. In JELIA, Springer, 200–212.Google Scholar
Gelfond, M. 2002. Representing Knowledge in A-Prolog. In Computational Logic: Logic Programming and Beyond, Springer Verlag, 413–451.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The Stable Model Semantics for Logic Programming. In International Conf. and Symp. on Logic Programming, MIT Press, 1070–1080.Google Scholar
Kemp, D.B. and Stuckey, P. J. 1991. Semantics of Logic Programs with Aggregates. In ISLP, MIT Press, 387–401.Google Scholar
Mumick, I. S., Pirahesh, H., and Ramakrishnan, R. 1990. The Magic of Duplicates and Aggregates. In Int. Conf. on Very Large Data Bases, Morgan Kaufmann, 264–277.Google Scholar
Pelov, N. 2004. Semantic of Logic Programs with Aggregates. Ph.D. thesis, Katholieke Universiteit Leuven.Google Scholar
Pelov, N., Denecker, M., and Bruynooghe, M. 2003. Translation of Aggregate Programs to Normal Logic Programs. In ASP: Advances in Theory and Implementation, CEUR Workshop Proceedings. 29–42.Google Scholar
Pelov, N., Denecker, M., and Bruynooghe, M. 2004. Partial Stable Models for Logic Programs with Aggregates. In LPNMR, Springer, 207–219.Google Scholar
Ross, K. A. and Sagiv, Y. 1997. Monotonic Aggregation in Deductive Database. J. Comput. Syst. Sci. 54, 1, 79–97.CrossRefGoogle Scholar
Son, T. C., Pontelli, E., and Elkabani, I. 2005. A Translational Semantics for Aggregates in Logic Programming. Tech. Rep. CS-2005-006, New Mexico State University. www.cs.nmsu.edu/CSWS/php/techReports.php?rpt_year=2005.Google Scholar
Zaniolo, C., Arni, N., and Ong, K. 1993. Negation and Aggregates in Recursive Rules: the LDL++ Approach. In DOOD. 204–221.CrossRefGoogle Scholar
You have
Access
- 42
- Cited by