Constraint Answer Set Programming without Grounding
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The s(CASP) system solves the grounding problem by performing a top-down goal-oriented search which eliminates the need for grounding.
“The s(CASP) system [1] solves this problem by performing a top-down goal-oriented search which eliminates the need for grounding.”
From Autonomous Task Completion Based on Goal-directed Answer Set Programming (2025) · cites this paper as [1]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 12
- ARIAS, J. 2016. Tabled CLP for Reasoning over Stream Data. In Technical Communications of the 32nd Int'l Conference on Logic Programming (ICLP'16). Vol. 52. OASIcs, 1-8. Doctoral Consortium.
- ARIAS, J. AND CARRO, M. 2016. Description and Evaluation of a Generic Design to Integrate CLP and Tabled Execution. In 18th Int'l. ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP'16). ACM Press, 10-23.
- BREWKA, G., EITER, T., AND TRUSZCZY ŃSKI, M. 2011. Answer Set Programming at a Glance. Communications of the ACM 54, 12, 92-103.
- CALIMERI, F., COZZA, S., AND IANNI, G. 2007. External Sources of Knowledge and Value Invention in Logic Programming. Annals of Mathematics and Artificial Intelligence 50, 3-4, 333-361.
- DOVIER, A., FORMISANO, A., AND PONTELLI, E. 2005. A Comparison of CLP(FD) and ASP Solutions to NP-Complete Problems. In International Conference on Logic Programming. Springer, 67-82.
- GABBRIELLI, M. AND LEVI, G. 1991. Modeling Answer Constraints in Constraint Logic Programs. In Proc. Eighth Int'l Conf. on Logic Programming.
- GELFOND, M. AND LIFSCHITZ, V. 1988. The Stable Model Semantics for Logic Programming. In International Conference on Logic Programming 1988. 1070-1080.
- HERMENEGILDO, M. V., BUENO, F., CARRO, M., L ÓPEZ, P., MERA, E., MORALES, J., AND PUEBLA, G. 2012. An Overview of Ciao and its Design Philosophy. Theory and Practice of Logic Programming 12, 1-2 (January), 219-252. http://arxiv.org/abs/1102.5497. · arXiv
- H ÖLLDOBLER, S. AND SCHWEIZER, L. 2014. Answer Set Programming and clasp, a Tutorial. In Young Scientists' International Workshop on Trends in Information Processing (YSIP). 77. HOLZBAUR, C. 1995. OFAI CLP(Q,R) Manual, Edition 1.3.3. Tech. Rep. TR-95-09, Austrian Research Institute for Artificial Intelligence, Vienna.
- JAFFAR, J. AND MAHER, M. 1994. Constraint Logic Programming: A Survey. Journal of Logic Programming 19/20, 503-581.
- JI, J., WAN, H., WANG, K., WANG, Z., ZHANG, C., AND XU, J. 2016. Eliminating Disjunctions in Answer Set Programming by Restricted Unfolding. In IJCAI. 1130-1137.
- MARPLE, K., SALAZAR, E., AND GUPTA, G. 2017b. Computing Stable Models of Normal Logic Programs Without Grounding. CoRR abs/1709.00501. · arXiv
Cited by
Sorted by citations
Fifty Years of Prolog and Beyond
KÖRNER, P., LEUSCHEL, M., BARBOSA, J., COSTA, V. S., DAHL, V., HERMENEGILDO, M. V., MORALES, J. F., WIELEMAKER, J., DIAZ, D., ABREU, S., et al. (2022) · Theory and Practice of Logic Programming · doi:10.1017/s1471068422000102 · Cited by 40 · see citing works
Reliable Natural Language Understanding with Large Language Models and Answer Set Programming
Rajasekharan, A., Zeng, Y., Padalkar, P., & Gupta, G. (2023) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.385.27 · Cited by 26 · see citing works
Self-citationLi, F., Zuo, F., & Gupta, G. (2025) · arXiv · doi:10.48550/arxiv.2512.04908 · Cited by 1 · see citing works
“Though computing ASP programs is considered to be NP-hard, there are a lot of ASP solvers (e.g., CLINGO [6], DLV [2], s(CASP) [3]) that can compute stable models of an ASP program efficiently.”
Self-citationAutonomous Task Completion Based on Goal-directed Answer Set Programming
Tudor, A. R. (2025) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.416.39
- Authors
- ARIAS, J., CARRO, M., SALAZAR, E., MARPLE, K., & GUPTA, G.
- Affiliations
- IMDEA Software Institute (ES)
- The University of Texas at Dallas (US)
- Venue
- Theory and Practice of Logic Programming
- Publisher
- Cambridge University Press (CUP)
- Published
- 2018-07
- Volume
- 18
- Issue
- 3-4
- Pages
- 337-354
- ISSN
- 1471-0684 (ISSN-L)
- 1475-3081
- OpenAlex
- W2798954882
- Cited by
- 88
- References
- 0
- Citations by year
- 2026: 9 · 2025: 14 · 2024: 11 · 2023: 16 · 2022: 10 · 2021: 16 · 2020: 6 · 2019: 5 · 2018: 1
- FWCI
- 3.92
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Theory and Practice of Logic Programming (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (1718945, S2013/ICE-2731, 1423419)
- Comunidad de Madrid (S2013, S2013/ICE‐2731)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
- Physical Sciences › Computer Science › Computer Networks and Communications › Constraint Satisfaction and Optimization
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Keywords
- answer set programming, constraint solvers, CLP, logical variables, combinatorial explosion
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
