×

Constraint answer set programming without grounding. (English) Zbl 1451.68063

Summary: Extending ASP with constraints (CASP) enhances its expressiveness and performance. This extension is not straightforward as the grounding phase, present in most ASP systems, removes variables and the links among them, and also causes a combinatorial explosion in the size of the program. Several methods to overcome this issue have been devised: restricting the constraint domains (e.g., discrete instead of dense), or the type (or number) of models that can be returned. In this paper we propose to incorporate constraints into s(ASP), a goal-directed, top-down execution model which implements ASP while retaining logical variables both during execution and in the answer sets. The resulting model, s(CASP), can constrain variables that, as in CLP, are kept during the execution and in the answer sets. s(CASP) inherits and generalizes the execution model of s(ASP) and is parametric w.r.t. the constraint solver. We describe this novel execution model and show through several examples the enhanced expressiveness of s(CASP) w.r.t. ASP, CLP, and other CASP systems. We also report improved performance w.r.t. other very mature, highly optimized ASP systems in some benchmarks.

MSC:

68N17 Logic programming
68T30 Knowledge representation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alferes, J. J.; Pereira, L. M.; Swift, T., Abduction in Well-Founded Semantics and Generalized Stable Models via Tabled Dual Programs, Theory and Practice of Logic Programming, 4, 4, 383-428, (2004) · Zbl 1090.68014
[2] Alviano, M.; Faber, W.; Greco, G.; Leone, N., Magic Sets for Disjunctive Datalog Programs, Artificial Intelligence, 187, 156-192, (2012) · Zbl 1251.68051
[3] Arias, J., (2016)
[4] Arias, J.; Carro, M., (2016)
[5] Balduccini, M.; Lierler, Y., Constraint Answer Set Solver EZCSP and why Integration Schemas Matter, Theory and Practice of Logic Programming, 17, 4, 462-515, (2017) · Zbl 1379.68038
[6] Banbara, M.; Kaufmann, B.; Ostrowski, M.; Schaub, T., Clingcon: The Next Generation, Theory and Practice of Logic Programming, 17, 4, 408-461, (2017) · Zbl 1379.68040
[7] Baselice, S.; Bonatti, P. A., A Decidable Subclass of Finitary Programs, Theory and Practice of Logic Programming, 10, 4-6, 481-496, (2010) · Zbl 1205.68114
[8] Baselice, S.; Bonatti, P. A.; Criscuolo, G., On Finitely Recursive Programs, Theory and Practice of Logic Programming, 9, 2, 213-238, (2009) · Zbl 1166.68311
[9] Brewka, G.; Eiter, T.; Truszczyński, M., Answer Set Programming at a Glance, Communications of the ACM, 54, 12, 92-103, (2011)
[10] Calimeri, F.; Cozza, S.; Ianni, G., External Sources of Knowledge and Value Invention in Logic Programming, Annals of Mathematics and Artificial Intelligence, 50, 3-4, 333-361, (2007) · Zbl 1125.68026
[11] Clark, K. L.; Gallaire, H.; Minker, J., Logic and Data Bases, Negation as Failure, (1978), Plenum
[12] Dal Palù, A.; Dovier, A.; Pontelli, E.; Rossi, G., GASP: Answer Set Programming with Lazy Grounding, Fundamenta Informaticae, 96, 3, 297-322, (2009) · Zbl 1207.68118
[13] Dovier, A.; Formisano, A.; Pontelli, E., International Conference on Logic Programming, A Comparison of CLP(FD) and ASP Solutions to NP-Complete Problems, 67-82, (2005), Springer · Zbl 1165.68486
[14] Gabbrielli, M.; Levi, G., (1991)
[15] Gebser, M.; Kaminski, R.; Kaufmann, B.; Ostrowski, M.; Schaub, T.; Thiele, S., (2008)
[16] Gelfond, M.; Lifschitz, V., (1988)
[17] Gelfond, M.; Lifschitz, V., Classical Negation in Logic Programs and Disjunctive Databases, New Generation Computing, 9, 3, 365-386, (1991) · Zbl 0735.68012
[18] Gupta, G.; Bansal, A.; Min, R.; Simon, L.; Mallya, A., (2007)
[19] Hermenegildo, M. V.; Bueno, F.; Carro, M.; López, P.; Mera, E.; Morales, J.; Puebla, G., An Overview of Ciao and its Design Philosophy, Theory and Practice of Logic Programming, 12, 1, (2012) · Zbl 1244.68019
[20] Hölldobler, S.; Schweizer, L., (2014)
[21] Holzbaur, C., (1995)
[22] Jaffar, J.; Maher, M., Constraint Logic Programming: A Survey, Journal of Logic Programming, 19, 20, 503-581, (1994)
[23] Janhunen, T.; Kaminski, R.; Ostrowski, M.; Schellhorn, S.; Wanko, P.; Schaub, T., Clingo goes Linear Constraints over Reals and Integers, TPLP, 17, 5-6, 872-888, (2017) · Zbl 1422.68024
[24] Ji, J.; Wan, H.; Wang, K.; Wang, Z.; Zhang, C.; Xu, J., (2016)
[25] Marple, K.; Salazar, E.; Chen, Z.; Gupta, G., (2017)
[26] Marple, K.; Salazar, E.; Gupta, G., (2017)
[27] Revesz, P. Z., A Closed-Form Evaluation for Datalog Queries with Integer (Gap)-Order Constraints, Theoretical Computer Science, 116, 1, 117-149, (1993) · Zbl 0785.68026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.