We present the CIFF proof procedure for abductive logic programming with constraints, and we prove its correctness. CIFF is an extension of the IFF proof procedure for abductive logic programming, relaxing the original restrictions over variable quantification (allowedness conditions) and incorporating a constraint solver to deal with numerical constraints as in constraint logic programming. Finally, we describe the CIFF system, comparing it with state of the art abductive systems and answer set solvers and showing how to use it to program some applications. (To appear in Theory and Practice of Logic Programming - TPLP).
As expected (and as shown in Section below), delegating the checks to a finite-domain constraint solver results in performances an order of magnitude faster than any answer set solver. Note that the ASP community is aware of this problem and recently some work has been initiated on integrating ASP with constraint solvers, in an effort to reduce the grounding size and speed computation (e.g., @cite_4 @cite_12 ), but for limited forms of constraints and restricted combinations of logic programs and constraints.
@cite_4 @cite_12
2096621306 2049791401 1519044014 2012741612
We present a new approach to integrating Constraint Processing (CP) techniques into Answer Set Programming (ASP). Based on an alternative semantic approach, we develop an algorithmic framework for conflict-driven ASP solving that exploits CP solving capacities. A significant technical issue concerns the combination of conflict information from different solver types. We have implemented our approach, combining ASP solver clingo with the generic CP solver gecode , and we empirically investigate its computational impact. We introduce an approach to computing answer sets of logic programs, based on concepts successfully applied in Satisfiability (SAT) checking. The idea is to view inferences in Answer Set Programming (ASP) as unit propagation on nogoods. This provides us with a uniform constraint-based framework capturing diverse inferences encountered in ASP solving. Moreover, our approach allows us to apply advanced solving techniques from the area of SAT. As a result, we present the first full-fledged algorithmic framework for native conflict-driven ASP solving. Our approach is implemented in the ASP solver clasp that has demonstrated its competitiveness and versatility by winning first places at various solver contests. Answer set programming (ASP for short) is a declarative problem solving framework that has been recently attracting the attention of researchers for its expressiveness and for its well-engineered and optimized implementations. Still, state-of-the-art answer set solvers have huge memory requirements, because the ground instantiation of the input program must be computed before the actual reasoning starts. This prevents ASP to be effective on several classes of problems. In this paper we integrate answer set generation and constraint solving to reduce the memory requirements for a class of multi-sorted logic programs with cardinality constraints. We prove some theoretical results, introduce a provably sound and complete algorithm, and report experimental results showing that our approach can solve problem instances with significantly larger domains. We describe the design and implementation of a finite domain constraint solver embedded in a Prolog system using an extended unification mechanism via attributed variables as a generic constraint interface. The solver is essentially a scheduler for indexicals, i.e. reactive functional rules encoding local consistency methods performing incremental constraint solving or entailment checking, and global constraints, i.e. general propagators which may use specialized algorithms to achieve a higher degree of consistency or better time and space complexity.