Issue title: Special issue of the 24th RCRA International Workshop on “Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion”
Guest editors: Marco Maratea, Ivan Serina and Paolo Torroni
Affiliations: [a] Department of Mathematics and Computer Science, University of Calabria, via Pietro Bucci 30B, 87036 Rende (CS), Italy. [email protected] | [b] Department of Informatics, Bioengineering, Robotics and Systems Engineering, University of Genova, viale Francesco Causa 15, 16145 Genova (GE), Italy. [email protected]
Correspondence:
[*]
Address for correspondence: Department of Mathematics and Computer Science, via Pietro Bucci 30B, 87036 Rende (CS), Italy
Abstract: Modern, efficient Answer Set Programming solvers implement answer set search via non-chronological backtracking algorithms. The extension of these algorithms to answer set enumeration is nontrivial. In fact, adding blocking constraints to discard already computed answer sets is inadequate because the introduced constraints may not fit in memory or deteriorate the efficiency of the solver. On the other hand, the algorithm implemented by CLASP, which can run in polynomial space, requires to modify the answer set search procedure. The algorithm is revised in this paper so as to make it almost independent from the underlying answer set search procedure, provided that the procedure accepts as input a logic program and a list of assumption literals, and returns an answer set (and associated branching literals). In fact, thanks to an alternative view in terms of transition systems, the revised algorithm is suitable to easily accommodate the enumerate of models of other Boolean languages, among them classical models of propositional theories. On a pragmatic level, the paper presents two implementations of the enumeration algorithm, in WASP for answer set enumeration, and in GLUCOSE for classical models enumeration. The implemented systems are compared empirically to the state of the art solver CLASP.
Keywords: Answer Set Programming, Enumeration, Assumption Literals
