Answer Set Programming
ConceptAnswer Set Programming (ASP) is a declarative problem-solving paradigm based on the stable-model (answer set) semantics of logic programming. ASP encodes problems as first-order logic programs whose answer sets correspond to solutions, and is solved by general-purpose ASP systems such as clingo. It is valued for its expressive language, extensible encodings, and support for flexible multi-criteria optimization, and has been applied to problems including constrained combinatorial testing, timetabling, event-sequence testing, symmetry breaking, and constraint satisfaction.
First seen 7/7/2026
Last seen 7/7/2026
Evidence 5 chunks
Wiki v1
WIKI
Overview
Answer Set Programming (ASP) is a declarative paradigm for knowledge representation and combinatorial problem solving. In ASP, a problem is encoded as a logic program whose answer sets (stable models) correspond to the solutions of the problem, and solutions are computed by an off-the-shelf ASP solver [cd609c07].
A standard reference introduction to the syntax and semantics of ASP is the primer by Lifschitz and colleagues, intended as a handout for undergraduate and graduate courses on Artificial Intelligence and Logic Programming [arxiv:cs/0508100v1].
NEIGHBORHOOD
No graph connections found for this entity yet. It may appear in future ingestion runs.
explore full graph →RELATIONSHIPS
3 connectionscatnap uses ASP as its underlying formalism.
The encoding is written in ASP.
The encoding is written in ASP.
LINKED ENTITIES
4 linkscatnap USES Extracted graph relationship
ASP encoding for strength-2 CMCA finding USES Extracted graph relationship
ASP encoding for optimal strength-2 CMCA finding USES Extracted graph relationship
clingo USES_SOLVER Multiple evidence chunks identify clingo as the off-the-shelf ASP solver used by catnap, supporting lexicographic optimization and multi-threaded portfolio search.
CITATIONS
16 sources16 citations — click to expand
[1] ASP is a declarative paradigm in which a problem is encoded as a logic program whose answer sets correspond to solutions, solved by an off-the-shelf ASP solver. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[2] ASP provides a high-level modeling approach with an expressive language, extensible encodings, and flexible multi-criteria optimization. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[3] First-order ASP encodings are written in the gringo series 4 language and combined with fact-format instance descriptions before solving. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[4] ASP solvers such as clingo compute answer sets and natively support lexicographic optimization over multiple #minimize/#maximize statements with priorities given after @. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[5] A typical ASP choice rule uses cardinality bounds, e.g., 1 { assigned(R,I,A) : p(I,A) } 1 :- row(R); col(I)., selecting exactly one value per row and column. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[6] ASP integrity constraints are written as ':- Body.' to forbid answer sets whose body holds, as used in domain and coverage constraints. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[7] ASP optimization statements such as #minimize{ 1,R : activated(R) }. minimize the count of activated atoms, while #maximize with priority weights implements lexicographic multi-criteria optimization. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[8] catnap is an ASP-based system that finds Constrained Mixed-level Covering Arrays (CMCAs) for Constrained Combinatorial Testing, combining a fact-format CCT instance with a first-order ASP encoding and delegating solving to clingo. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[9] The basic strength-2 CMCA finding encoding (Listing 2) generates rows, columns, and constraint identifiers; assigns exactly one value per cell; enforces domain constraints; and requires every valid (I,J,A,B) pair to be covered in some row. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[10] The optimal strength-2 CMCA finding encoding (Listing 3) introduces activated/1 atoms whose count is minimized and assigns values only to activated rows. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[11] The weakened encoding (Listing 4) converts coverage constraints to soft constraints via #maximize, uses lexicographic optimization across size and coverage priorities, and avoids the pre-calculation of valid pairs required by earlier dedicated implementations. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[12] Empirically, catnap found the best known bounds on 25 benchmark instances versus 34 (TCA), 15 (CASA), 0 (ACTS), and 0 (Cascade), and improved the bound on the large benchmark_gcc instance to 15. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[13] Event-sequence testing ASP encodings use #maximize over covered atoms to greedily generate maximal-coverage test cases and to produce strength-t test suites of maximal (t+1)-coverage for early failure detection. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[14] Constraint ASP (CASP) extends ASP to declaratively represent and solve finite linear Constraint Satisfaction Problems, with solvers such as clingcon. catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming
[15] Symmetry detection for ASP can be reduced to a graph automorphism problem, with symmetry-breaking constraints encoded as permutation cycles; this approach has been extended to constraint ASP solving and distributed nonmonotonic multi-context systems. Symmetry Breaking for Answer Set Programming
[16] A primer on the syntax and semantics of Answer Set Programming intended as a handout for AI and Logic Programming courses is available on arXiv. A primer on Answer Set Programming