1

Preprint

Sketched Answer Set Programming

arXiv:1705.07429v1 [] 21 May 2017

Sergey Paramonov1 ( ), Christian Bessiere2 , Anton Dries1 , Luc De Raedt1
1 KU Leuven, 2 U. Montpellier, CNRS
(e-mail: sergey.paramonov@kuleuven.be)

submitted 1 January 2003; revised 1 January 2003; accepted 1 January 2003

Abstract
Answer Set Programming (ASP) is a powerful modeling formalism for combinatorial problems. However,
writing ASP models is not trivial. We propose a novel method, called Sketched Answer Set Programming
(SkASP), aiming at supporting the user in resolving this issue. The user writes an ASP program while
marking uncertain parts open with question marks. In addition, the user provides a number of positive
and negative examples of the desired program behaviour. The sketched model is rewritten into another ASP
program, which is solved by traditional methods. As a result, the user obtains a functional and reusable ASP
program modelling her problem. We evaluate our approach on 21 well known puzzles and combinatorial
problems inspired by Karps 21 NP-complete problems and demonstrate a use-case for a database application
based on ASP.
KEYWORDS: Answer Set Programming; Relational Learning; Constraint Learning

1 Introduction
Many AI problems can be formulated as constraint satisfaction problems that can be solved by
state-of-the-art constraint programming (CP) (Rossi et al., 2006) or answer set programming
(ASP) techniques (Lifschitz, 2008). Although these frameworks provide declarative representations that are in principle easy to understand, writing models in such languages is not always
easy.
On the other hand, for traditional programming languages, there has been significant attention
for techniques that are able to complete (Lezama, 2013) or learn a program from examples (Gulwani et al., 2015). The idea of program sketching is to start from a sketched program and some
examples to complete the program. A sketched program is essentially a program where some
of the tests and constructs are left open because the programmer might not know what exact
instruction to use. For instance, when comparing two variables X and Y , the programmer might
not know whether to use X < Y or X ≤ Y or even X + 1 < Y . By providing a few examples of
desired program behaviour, the sketched program can then be completed.
In this paper, we show that sketches can be used in ASP. We develop a method (based on ASP
itself) to complete such sketched answer set programs. We also argue that this can be useful when
writing ASPs, especially when having already identified the potentially problematic parts of a
model. In this regard, SkASP differs from traditional debugger, which can be used to locate where
the model is wrong. But typical debuggers provide only little support for repairing such bugs once
they have been located. SkASP, in contrast, provides a constructive solution for repairing such
bugs or completing partial programs by using examples together with sketched variables.

2

Sergey Paramonov, Christian Bessiere, Anton Dries, Luc De Raedt

Assume that a user needs to solve the Peacefully Coexisting Armies of Queens, which is a
version of the n-queens problem with black and white queens, where queens of the same color
do not attack each other. Assume that the user has quickly written the following version of the
program, which might have been inspired by a solution written in the constraint programming
language Essence available from the CSP library (Özgür, 2015). In the (erroneous) program
below, the Rw (Cb ) stand for the variable representing the row (column) of a white (black) queen:
← queen(w, Rw ,Cw ), queen(b, Rb ,Cb ), Rw 6= Rb .
← queen(w, Rw ,Cw ), queen(b, Rb ,Cb ),Cw 6= Cb .
← queen(w, Rw ,Cw ), queen(b, Rb ,Cb ), |Rw − Rb | 6= |Cw −Cb |.

Intuitively, the program specifies constraints on the relationship between two queens on the
rows (first rule), columns (second rule) and diagonals (third rule). Now assume that the user realizes that the program is wrong and he might have been to quick. What sketching allows to do
in such cases is to mark the potentially erroneous predicates with question marks, to specify possible alternatives and to provide a few examples of the intended behaviour. Figure 1d describes a
possible sketch for this problem. It basically states that it is unknown whether the 6= is correct in
the first two rules, and whether the arithmetic operation is correct. By using a few positive and
negative examples, as well as the built-in alternatives for ?= (from its domain =, 6=, <, >, ≤, ≥)
and for ?+ (from arithmetic operations), the SkASP solver will produce the correct answer set
program.
Below, in Section 2, we introduce the problem of sketched Answer Set Programming. In Section 3, we show how to transform a sketched ASP into a form that can be solved by a regular
ASP solver and analyze its theoretical properties. More specifically, we demonstrate that there is
no complexity jump with respect to the complexity of existence of answer sets of a regular ASP
program. In Section 4, we evaluate our approach on a set of classical NP-complete problems
(inspired by Karp’s 21 NP-complete problems). In Section 5, we demonstrate an application of
our method to a database system based on ASP. Finally, we discuss related work in Section 6,
and conclude in Section 7.

2 ASP and Sketching
Answer Set Programming (ASP) is a form of declarative programming based on the stable model
semantics (Gelfond and Lifschitz, 1988) of logic programming (Lifschitz, 2008). We follow
the standard syntax and semantics of ASP as described in the Potassco project (Gebser et al.,
2012). A program is a set of rules of the form a ← a1 , . . . ak , not ak+1 , . . . , not an . where a is a
propositional atom, called a head, and for i between 1 and k, ai is a positive propositional atom
and for i between k + 1 and n, ai is a negative propositional atom. All these atoms ai together
are referred to as the body. A positive or negative atom is called a literal. A rule of the form
a ← . is called a fact and abbreviated as a. and a rule without a head is called an integrity
constraint. Conditional literals, written as a : l1 , . . . , ln , and cardinality constraints, written as
cmin {l1 , . . . , ln }cmax , are used (l1 , . . . , ln are literals here, and cmin , cmax are non negative integers).
A conditional atom holds if its condition is satisfied and a cardinality constraint is satisfied if
between cmin and cmax literals hold in it. Furthermore, as ASP is based on logic programming
and also allows for variables, denoted in upper-case, the semantics of a rule or expression with
a variable is the same as that of its set of ground instances. We restrict the ASP language to the

Sketched Answer Set Programming
[SKETCH]
reached(Y) :- cycle(a,Y).
reached(Y) :- cycle(X,Y),
reached(X).
:- ?p(Y), ?not ?q(Y).
[EXAMPLES]
positive: cycle(a,b). cycle(b,c).
cycle(c,a).
negative: cycle(a,b). cycle(b,a).
[SKETCHEDVAR]
?p/1 : node, reached
?q/1 : node, reached
[FACTS]
node(a). node(b). node(c).
[EXAMPLES]
positive: cycle(a,b). cycle(b,c).
cycle(c,a).
negative: cycle(a,b). cycle(b,a).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3

%%%%% EXAMPLES AND DECISIONS %%%%%%
positive(0). cycle(0,a,b). cycle(0,b,c). cycle(0,c,a).
sketched_q_choice(c_node). sketched_q_choice(c_reached).
1 { decision_q(X) : sketched_q_choice(X) } 1.
1 { decision_not(positive); decision_not(negative) } 1.
%%%%% INFERENCE RULES %%%%%%
sketched_q(E,c_node,X0) :- node(X0),examples(E).
sketched_q(E,c_reached,X0) :- reached(E,X0).
reached(E,Y) :- cycle(E,a,Y),examples(E).
reached(E,Y) :- cycle(E,X,Y),reached(E,X),examples(E).
sketched_not(E,positive,Q,Y) :- sketched_q(E,Q,Y).
sketched_not(E,negative,Q,Y) :- not sketched_q(E,Q,Y),dom1(Y),...
%%%%% POSITIVE SKETCHED RULES %%%%%%
:- sketched_p(E,P,Y),sketched_not(E,Not_D,Q,Y),decision_p(P),
decision_q(Q),decision_not(Not_D),positive(E).
%%%%% NEGATIVE SKETCHED RULES %%%%%%
neg_sat(E) :- sketched_p(E,P,Y),sketched_not(E,Not_D,Q,Y),
decision_p(P),decision_q(Q),decision_not(Not_D),negative(E).
:- not neg_sat(E), negative(E).

(a) Hamiltonian Cycle (the original ASP encoding from Gebser (b) The core of rewritten Listing 1a in ASP (we only show predicate q,
since it is similar for p; domain declaration, facts, etc omitted)
et al. (2012))
[SKETCH]
% constraints rows,cols,squares
:-c(X,Y,N), c(X,Z,M), Y ?= Z,
N ?= M.
:-c(X,Y,N), c(Z,Y,M), X ?= Z,
N ?= M.
insq(S,N) :-c(X,Y,N), sq(S,X,Y).
:-num(N),sqrs(S),?not insq(S,N).
[EXAMPLES]
positive: c(1,1,6). c(1,2,9)...

1
2
3
4
5
6
7
8
9
10

[SKETCH]
:- q(w,Rw,Cw), q(b,Rb,Cb),
Rw ?=
:- q(w,Rw,Cw), q(b,Rb,Cb),
Cw ?=
:- q(w,Rw,Cw), q(b,Rb,Cb),
Rw ?+ Rb ?= Cw ?+
[EXAMPLES]
positive: q(w,1,1). q(w,2,2).
negative: q(b,2,2). q(w,3,1).

Rb.
Cb.
Cb.
...
...

[SKETCH]
% constraints on rows and columns
:- c(X,Y,N), c(X,Z,M), Y ?= Z,
N ?= M.
:- c(X,Y,N), c(Z,Y,N), X ?= X,
N ?= M.
[EXAMPLES]
positive: c(1,1,a). c(1,2,b)...
negative: c(1,1,b). c(1,2,a)...

(e) Latin Square (based on Su(c) Sudoku sketch (ASP due (d) B&W Queens sketch (q for doku)
to Hölldobler and Schweizer queen; core)
(2014);c stands for cell)
Fig. 1: Collection of sketches and an example of rewriting used in the paper

NP-complete subset specified here. For more details on ASP, see Gebser et al. (2012); Eiter et al.
(2009).
We extend the syntax of ASP with sketched language constructions. Instead of allowing atoms
of the form p(t1 , ...,tn ), where p/n is a predicate and the ti are terms (variables or constants),
we now allow to use sketched atoms of the form ?q(t1 , ...,tn ) where ?q is a sketched predicate
variable with an associated domain dq containing actual predicates of arity n. The meaning of
the sketched atom ?q(t1 , ...,tn ) is that it can be replaced by any real atom p(t1 , ...,tn ) provided
that p/n ∈ dq . It reflects the fact that the programmer does not know which p/n from dq should
be used. Sketched atoms can be used in the same places as any other atom.
We also provide some syntactic sugar for some special cases and variants, in particular, we
use a sketched inequality X ?= Y , a sketched arithmetic operator X ?+ Y ,1 and sketched negation
?not p(X). The domain of X ?= Y is the set {=, 6=, <, >, ≥, ≤, >}, where > is the atom that
is always satisfied by its arguments, the domain of X ?+ Y is the set {+, −, ×, ÷, dist} where
dist(a, b) is defined as |a − b|, and the domain of ?not is {0,
/ not}. An example of sketched inequality can be seen in Line 3 of Figure 1c, examples of sketched predicates and negation in Line
4 of Figure 1a and sketched arithmetic in Line 5 of Figure 1d.

1

Strictly speaking this is not a sketched predicate but a sketched operator, but for convenience we will only make this
distinction where needed.

4

Sergey Paramonov, Christian Bessiere, Anton Dries, Luc De Raedt

A sketched variable is a sketched predicate, a sketched negation, a sketched inequality or
a sketched arithmetic operator. We refer to the set of all sketched variables as S. Predicate p
directly depends on predicate q iff q occurs in the body of a rule with p in the head or p is a
sketched predicate and q is in its domain. We say that p depends on q iff q is in the transitive
closure of all predicates on which p directly depends. An example is a set of ground atoms.
A preference is a function from S to Z. A substitution θ is preferred over θ 0 given preferences
f iff for all si 7→ di ∈ θ and si 7→ di0 ∈ θ 0 it holds that f (di ) ≥ f (di0 ) and at least one inequality is
strict.
Definition 1 (Sketched Answer Set Problem (SkASP))
Given a sketched answer set program P with sketched variables S of domain D and preferences
f , and positive and negative sets of examples E+ and E− , the Sketched Answer Set Problem is to
find all substitutions θ : S 7→ D preferred by f such that Pθ ∪ e has an answer for all e in E+ and
for no e in E− . The decision version of SkASP asks whether there exists such a substitution θ .
E.g., Figure 1a represents a sketch of Hamiltonian Cycle with P being the rules in Lines 2, 4, 5
and S={?p, ?q, ?not}, D={{reached/1, node/1} p , {reached/1, node/1}q , {0,
/ not}not },
E+ ={{cycle(a, b), cycle(b, c), cycle(c, a)}}, E− ={{cycle(a, b), cycle(b, a)}} and f ≡ 1.
It will be useful to distinguish different versions w.r.t. the preferences. First, when f (θ ) is
constant, all substitutions are equal and there are no preferences. While this suffices in many
cases, it is often useful to express preferences over the substitutions. Because this might impose
an extra burden on the user, we also provide default preferences for the built-in sketched variables
(like inequality, negation and arithmetic), cf. the experiments in Section 4.

3 Rewritting Schema
The key idea behind our approach is to rewrite a SkASP problem (P, S, D, f , E+ , E− ) into an
ASP program such that the original sketching program has a solution iff the ASP program has an
answer set. This is achieved by 1) inserting decision variables into the sketched predicates, and
2) introducing example identifiers in the predicates.
The original SkASP problem is then turned into an ASP problem on these decision variables
and solutions to the ASP problem allow to reconstruct the SkASP substitution.
The rewriting procedure has four major steps: example expansion, substitution generation,
predicate reification and constraint splitting.
Example Identifiers To allow the use of multiple examples in the program, every relevant predicate is extended with an extra argument that represents the example identifier. The following
steps are used to accommodate this in the program.
1. Let SP be the set of all predicates that depend on a predicate occurring in one of the
examples.
2. Replace each literal p(t1 , ...,tn ) for a predicate p ∈ SP in the program P by the literal
p(E,t1 , ...,tn ), where E is a variable not occurring in the program.
3. Add the literal examples(E) as a guard to the body of each rule in P.
4. For each atom p(t1 , ...,tn ) in the i-th example, add the fact p(i,t1 , ...,tn ) to P.
5. For each positive example i, add the fact positive(i) to P, and for each negative one, the
fact negative(i).

Sketched Answer Set Programming

5

As an example the rule in Line 2 of Figure 1a becomes Line 9 of Figure 1b, and the example in
Line 16 corresponds to rewritten Line 2.
Substitution Generation We now introduce the decision variables:
1. For each sketched variable si with domain di , add the following constraint to P:
1 {decision si (X) : di (X)} 1.
2. For each value v in di , add the fact di (v).
This constraint ensures that each answer set has exactly one value from the domain assigned
to each sketched variable. This results in a one-to-one mapping between decision atoms and
sketching substitution θ . An example can be see in Lines 4 and 5 of Figure 1b.
Predicate Reification We now introduce the reified predicates,
1. Replace each occurrence of a sketched atom s(t1 , ...,tn ) in a rule of P with the atom
reified s(D,t1 , . . . ,tn ), and add decision s(D) to the body of the rule.
2. For each sketched variable s and value di in its domain, add the following rule to P:
reified s(di , X1 , . . . , Xn ) ← di (X1 , . . . , Xn ).
where the first argument represents the decision variable for s.
Thus, semantically reified s(di , X1 , . . . , Xn ) is equivalent to di (X1 , . . . , Xn ) and decision s(di ) indicates that the predicate di has been selected for the sketched variable s. Notice that we focused
here on the general case of a sketched predicate ?p(. . . ). It is straightforward to adapt this for
the sketched inequality, negation and arithmetic operator. Examples of reification can be seen in
Lines 7 of Figure 1b for the sketched ?q of the sketch in Figure 1a and in Lines 11, 12 for an
example of reified negation.
Integrity Constraint Splitting
1. Replace each integrity constraint ← body by:
← body, positive(E)
negsat(E) ← body, negative(E)
2. And add the rule to the program:
← negative(E), not negsat(E).
This will ensure that all positives and none of the negatives have a solution. For example, the
constraint in Line 5 of Figure 1a is rewritten into a positive constraint in Lines 14, 15 and into a
negative in Lines 17, 18.
Another important result is that the preferences do not affect the decision complexity. Proofs
can be found in the supplementary materials.
Lemma 1 (Preferences do not affect the decision version of SkASP)
A sketched ASP program (P, S, D, f , E+ , E− ) has a satisfying substitution θ 0 (preferred) iff (P, S, D, 1, E+ , E− )
has a satisfying substitution θ , where 1(x) ≡ 1 is the constant function, i.e., no preferences.
Let us state the key property of this rewriting:

6

Sergey Paramonov, Christian Bessiere, Anton Dries, Luc De Raedt

Theorem 1 (Sound and Complete Sketched Rewriting)
A sketched ASP program (P, S, D, f , E+ , E− ) has a satisfying substitution θ iff the rewritten ASP
program P0 has an answer set.
Interestingly, the sketched ASP problem has the same complexity as the original ASP program.
Theorem 2 (Complexity of Sketched Answer Set Problem)
The decision version of SkASP is NP-complete.
Proof
Membership. Follows from the encoding of SkASP into a fragment of ASP which is in NP.
Completeness. Let P0 be an arbitrary answer set program, then the question of whether it has
an AS is reduced to asking if an empty θ satisfies the following SkASP: consider S = 0,
/ E− =
+
0
0
0,
/ E = {0},
/ f ≡ 1 and P = P . If θ satisfies the SkASP, then P and consequently P have an
answer set.
Dealing with preferences Preferences are, as we shall show in our experiments, useful to restrict
the number of solutions. Currently, we have implemented preferences using a post-processing
approach (which will also allow to apply the schema to other formalism such as CP or IDP
(Bruynooghe et al., 2013)), in which we first generate the set of all solutions O (without taking
into account the preferences), and then post-process O. Basically, we filter out from O any solution that is not preferred (using tests on pairs (o, o0 ) from O × O). Note that the preferences
introduce a partial order on the solutions. In future work, we plan to make the search more effective by using the preferences in the search process (using ASP extensions (Brewka et al., 2015))
or by formulating the SkASP task as an optimisation problem (using built-in ASP constructs).
4 Experimental Evaluation
For the experimental evaluation we have created a dataset consisting of 21 classical combinatorial problems among which most are NP-complete. Our dataset contains Graph Clique; 3D
Matching; Vertex and Edge Coloring; Vertex and Edge Domination; Exact, Vertex and Clique
Covers; Sudoku; Latin Square; B&W and n-Queens; Hitting Set; Hamiltonian Cycle; Feedback
Vertex and Arc Sets; Radio Frequency Assignment (FA); Set Packing and Splitting; Subgraph
Isomorphism. For more detailed dataset description we refer to Appendix A.
All problems, their code, and implementation details, can be found in the accompanying
Github repository: https://github.com/SergeyParamonov/sketching
Implementation details and limitations. The SkASP engine is written completely in Python 3.4
and requires the library pyasp to work. All examples have been run in a 64-bit Ubuntu 14.04
environment. The current implementation does not support language constructs such as choice
rules and aggregates in the rules of sketched ASP.
Sketches. For many problems there are already existing ASP encodings that we sketched and
tried to reconstruct, such as Sudoku in Figure 1c from Hölldobler and Schweizer (2014) or
Hamiltonian Cycle in Figure 1a from Gebser et al. (2012). For the ones without an ASP encoding, we followed a canonical ASP encoding strategy of generate-and-test to create ASP encodings that should be reconstructed by our method.

Sketched Answer Set Programming

7

(a) Problems convergence without preferences (with (b) Average number of solutions over the dataset,
5 sketched variables): B&W Queens (from Figure split into the easy group converging without prefer1d) and FAP converge, while Sudoku does not
ences and hard not converging

Fig. 2: Investigating Q1 : problems convergence without preferences (left), averaged across the
dataset (right); log-scale; the number of sketched indicated in parentheses
We use the default preferences in the experimental section for the built-in inequality sketch
X ?= Y : namely = and 6= have equal maximal preference, this preference still implies a partial
order. A user can redefine the preferences by giving them weights. Our experiments indicate that
for other sketched types no default preferences are needed.
Combinatorial explosion. One might consider a baseline approach that would enumerate all instances of the ASP sketch, and in this way produce one ASP program for each assignment that
could then be tested on the examples. This naive grounding and testing approach is, however, infeasible: the number of possible combinations grows exponentially with the number of sketched
variables. For example, for the Radio Frequency Problem there are around 100,000 possible assignments to the sketched variables. If we multiply them by the number of examples, around a
million ASP programs would have to be generated and tested. This is infeasible in practice.
Experimental questions. We investigate the following experimental questions here:
• Q1 : What is the relationship between the number of examples and the number of solutions?
How many examples does it take to converge?
• Q2 : Are preferences useful?
• Q3 : What is the effect of the number of sketched variables on the number of examples
needed to converge?
• Q4 : What is the effect of the number of sketched variables and the example size (in atoms)
on the runtime?
• Q5 : What is the effect of encoding variations on the number of solutions and runtime?
We investigate Q1 by measuring the impact of the number of examples on the number of
solutions of the 21 SkASP problems. For each problem we provide up to 7 examples manually
created and provided in the Github repository. An interesting observation is that even if the
user wants to solve, say the Latin Square 20 × 20, she does not need to provide examples of
size 20 · 20 = 400. She can simply provide examples on the Latin Square 3 × 3 and our SkASP
problem will learn the generic Latin Square program (see the sketch in Figure 1e).
Figure 2a reports the number of solutions for some of our 21 SkASP problems when increasing
the number of examples. We observe that in some cases, 7 examples are sufficient to converge to
a single solution e.g., FAP, B&W Queens.

8

Sergey Paramonov, Christian Bessiere, Anton Dries, Luc De Raedt

(a) Between 2 and 7 examples are (b) The effect of the number of (c) Dependency between the numneeded to reach the unique solu- sketched variables on the solutions ber of sketched variables and solution (or a small group of equiva- with preferences (FAP)
tions without preferences (FAP)
lent) under preferences.

Fig. 3: Investigating Q2 and Q3 : dependency for the number of solutions for each problem (left;
problems converging on the 2nd example are not depicted), the effect of different number of
sketched variables (middle and right); log-scale; the number of sketched indicated in parentheses

On some other problems, however, after 7 examples there still remain many solutions (on
average 18 for problems that do not converge). Figure 2b reports the same information as Figure
2a for all 21 problems: the average on the 21 problems; the average on the 9 that converge within
7 examples, referred to as the easy problems; and the average on the 12 that still have several
solutions after 7 examples, referred to as the hard problems. When SkASP does not converge
to a unique solution, this leaves the user with choices, often amongst equivalent ASP programs,
which is undesirable.
For problems that do not converge after a few examples, we propose to use preferences, as
provided by our SkASP framework. We use the default preference setting described earlier: for
the built-in inequality sketch X ?= Y = and 6= have equal maximal preference, all other relations
have the minimal one; for other sketched types no preferences are used.
We investigate Q2 by measuring again the impact of the number of examples on the number
of solutions. In Figure 3a, we observe that all problems have converged in less than 7 examples
(under default preferences). The impact of preferences on the speed of convergence is even more
visible on the whole set of problems, as reported in Figure 2b. The number of solutions with
preferences is smaller, and often much smaller than without preferences, whatever the number of
examples provided. With preferences, all our 21 problems are learned with 7 examples.
To answer Q3 , we look into the convergence of FAP by varying the number of sketched variables. The original sketched program of FAP contains 5 sketched variables. We vary it from 2 to
5 by turning 3, 2, 1, or 0 sketched variables into their actual value. As expected, in Figure 3b,
we observe that the more there are sketched variables in the SkASP, the slower the number of
solutions decreases. Furthermore, the number of sketched variables has a greater impact on the
convergence without preferences, as we see in Figure 3c. After 3-5 examples under preferences
we have fewer than 10 solutions, while without preferences there are still dozens or hundreds of
solutions.
To address Q4 , we set up the following experiment: we have taken the standard 9 × 9 Sudoku
encoding (Hölldobler and Schweizer, 2014) and varied the number of sketched inequalities in it.
We then run it against randomly generated positive and negative examples (in equal quantities).
The outcome is depicted in Figure 4a. We observe that the runtime depends on the number of
sketched variables, i.e. the runtime exhibits a linear behavior with the slope determined by the
number of sketched variables. To measure the effect of the examples size, i.e. the number of
ground facts in a single example, we set up the following experiment: for the n × n Latin Square

Sketched Answer Set Programming

9

(a) Sudoku: investigating the effect of different num- (b) Latin Square: the effect of the example size on
the runtime (the example size is quadratic in n)
ber of sketched variables on the runtime

Fig. 4: Investigating Q4 : the effect of the number of sketched variables (left) and of the example
size (right) on runtime

(which is adapted from the Sudoku encoding by removing the square constraints), we vary the
parameter n and measure the learning time on the random examples (in equal quantities). In
Figure 4b, we again observe a linear behavior. The slope depends on the size of an example,
which seems to be logical because the number and the size of examples directly affects the
grounding size. Interestingly, the quadratic growth of an example size shows only moderate effect
on the linear slope of the behavior.
To investigate Q5 , we have focused on the n-queens problem and collected several encodings
from multiple sources: Potascco, Hakank.org, an ASP introductory course by Tran Cao Son (New
Mexico State University)2 and our encoding. Whereas all the encodings model the same problem
they show significant variations in expressing constraints. To reduce the bias in how the sketched
variables are introduced and how examples are created, we pick sketched variables randomly
(inequalities and arithmetic) and we also randomly generate examples (positive and negative) in
equal quantities. For each encoding we have introduced 5 sketched variables and measured the
number of solutions and runtime on 100 random examples (since the examples are random, there
is no guarantee of diversity, which of course affects the overall number of solutions). The results
have been averaged over 100 runs. 3
In Figure 5b we see that while the encodings show certain variability in the runtime, they
demonstrate a similar growing runtime pattern and there is no significant (e.g., of an order of
magnitude) difference in the runtime exhibited by the models. All models needed under 3 seconds (on average for 100 examples) to learn the constraints. In Figure 5a, we observe a similar
situation: while there is a certain variation in the number of solutions, they demonstrate similar
behavior. Of course, since the examples are random and are not designed to be diverse, we do
not have fast convergence as in Figures 3a and 2b.
Overall, we observe that only few examples are needed to converge to a unique or a small group
of equivalent solutions (provided that examples are diverse). An example where such equivalent

2

3

http://www.cs.uni-potsdam.de/~torsten/Lehre/ASP/Folien/asp-handout.pdf
http://www.hakank.org/answer_set_programming/nqueens.lp
https://www.cs.nmsu.edu/~tson/tutorials/asp-tutorial.pdf
While conducting this experiment, we stumbled upon a peculiar bug. One encoding worked mostly by pure luck.
The following constraint :- queen(X1,Y1), queen(X2,Y2), X1 < X2, abs(Y1 - X1) == abs(Y2 - X2).
works because abs is not actually absolute value but is an uninterpreted function, it essentially checks that iff X == Y ,
and that is indeed the solution found by our system. We have contacted the author and the model has been updated.

10

Sergey Paramonov, Christian Bessiere, Anton Dries, Luc De Raedt

(a) Measuring the number of solutions (default pref- (b) Measuring the runtime growth for various encoderences)
ings (in seconds)

Fig. 5: Investigating Q5 : what is effect of encoding variations on the number of solutions (left)
and on runtime (right). n-queen problem (5 sketched variables placed randomly; averaged over
100 runs; random examples).
solutions are found is the edge coloring problem, where two equivalent (for undirected graphs)
constraints are found:
← color(X,Y1 ,C), color(X,Y2 ,C), Y1 6= Y2 .
← color(X1 ,Y,C), color(X2 ,Y,C), X1 6= X2 .
These two syntactically different constraints are both equivalent for this problem and cannot be
differentiated by any valid example. In the experiments (with manually created examples) we
have only two such cases: the one described above and n-queens with three symmetric solutions
under the default preferences.
An interesting observation we made on these experiments is that the hardness (e.g., in terms
of runtime) of searching for a solution of a problem is not directly connected to the hardness of
learning the constraints of this problem. This can be explained by the fact that the search spaces
are incomparable. The SkASP searches through the search space of sketched variables, which
is usually much smaller than the search space of the set of decision variables of the problem to
learn.

5 Use-case: database query completeness
To illustrate SkASP on a real application of ASP, we consider the ASP solution for reasoning
about query completeness in databases, which is related to data quality issues (Nutt et al., 2015;
Razniewski and Nutt, 2011). According to Nutt et al. (2013), the problem of query completeness is to determine whether a conjunctive query (i.e., a positive Datalog rule) over a partially
complete database (a set of ground facts) can be answered completely. Table completeness rules
(i.e., positive Datalog rules) specify which parts of a database are complete. The problem then is
to decide whether these rules allow to retrieve exactly the same answers as if the database had
complete information.
We now consider an ASP implementation, called MAGIK (Savkovic et al., 2012), for reasoning about query completeness, which also uses various schema constraints (Nutt et al., 2015),4
4

Here we focus on functional dependences although it is easy to incorporate also other constraints.

Sketched Answer Set Programming

11

and which generates ASP code that allows to decide whether the query will be complete. More
formally, we consider the following notion of query completeness: a query completeness statement T is a rule of the form QT (X) ← R(X), G, where G is a conjunction of atoms. We denote
as T (D) the set of ground facts {R(x) | T ∪ D |= QT (x)}, i.e. the rule filters the database and
outputs the facts that are complete. A database D satisfies a foreign key fk if and only if for any
fact d it holds that D |= d ⇐⇒ D ∪ fk |= d. Let Q be a conjunctive query, T be a set of table
completeness rules and S be the set of schema constraints. Q is complete wrt to S and T if and
S
only if for any database D satisfying S it holds that Q(D) = Q( T ∈T T (D)).
Essentially, the MAGIK system generates three sets of ASP constraints: schema constraints,
table completeness (TC) rules and the query completeness check. The fine grained details are not
important here but the general idea is the following: a lot of TC rules might be accumulated over
time and entered into the system by a database administrator (see e.g., Lines 6-15 in Figure 6),
the query itself may be complicated and error-prone (see Line 17), whereas schema constraints
typically do not change over time (see Lines 3 and 4).
We use the following scenario to illustrate SkASP: assume that a user obtained the ASP code
via the MAGIK tool, including many TC rules, and that she is not aware of which ones are
still valid. Furthermore, assume that the user does not fully understand a certain detail in the
generated query check. What the user knows, however, is that the query is not complete without
the presence of the foreign key constraints. Let us illustrate this scenario on a school schema and
an accompanying conjunctive query:
Query:
Database Schema:
Extract all names of computer science pupils
pupil(ID,Name,Country)
Q(N) ← p(I,N,C), s(I,Mj,Mi), Mj = cs
specialization(ID,Major,Minor)
school(SID,Sname,PID,Region,Language)

p stands for pupil, s for specialization
We assume that there are two foreign key constraints:
school(S,Sn,Id,R,L) ← pupil(Id,N,C), domain school(S,Sn,R,L) and
school(S,Sn,Id,R,L) ← specialization(Id,Mj,Mi), domain school(S,Sn,R,L).
We encode uncertainty over which TC rule applies by creating a sketched constant ?true that
can be mapped to {>, ⊥} for each rule and appending it to each TC statement as a propositional
atom (Lines 6-15 in Figure 6). The way we specify uncertainty in the query is similar to the
examples before: we state that a certain atom, for instance an equality atom, is sketched (Line 17).
The schema constraints are encoded as normal rules with the activation guards that depend on the
examples (Lines 3 and 4). Then, we introduce a preference of ⊥ over > for the sketched ?true.
Running SkASP on the encoding gives us both a minimal set of TCs covering the examples (five
combinators are produced), and the assignment for the query (only one satisfies the examples).
This example shows how SkASP can be used in a fairly general setting as a useful autocompletion tool that allows to synthesize a correct combination of rules. If a user had to do this
manually, he would have to go through a painful search process whereby numerous combinations
would potentially have to be tested out.
6 Related Work
The problem of sketched ASP that we introduced is related to a number of topics. First, the idea of
sketching originates from the area of programming languages, where it relates to so called selfcompleting programs (Lezama, 2013), typically in C (Lezama, 2009) and in Java (Jeon et al.,

12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Sergey Paramonov, Christian Bessiere, Anton Dries, Luc De Raedt
[SKETCH]
% Schema constraints
sc(SId,Sn,Id,R,L) :- p(Id,N,C),
fresh_consts(SId,Sn,R,L), fk_holds(1).
sc(SId,Sn,Id,R,L) :- s(Id,Mj,Mi), fresh_consts(SId,Sn,R,L), fk_holds(2).
% TC statements
p_a(Id,N,C)
:- p(Id,N,C),
?true1.
s_a(Id,Mj,Mi)
:- s(Id,Mj,Mi),
?true2.
sc_a(SId,Sn,Id,R,L) :- sc(SId,Sn,Id,R,L),
?true3.
p_a(Id,N,C)
:- p(Id,N,C), s(Id,Mj,Mi), Mj = cs,
?true4.
s_a(Id,Mj,Mi)
:- s(Id,Mj,Mi), Mj = cs, p(I,N,C),
?true5.
sc_a(SId,Sn,Id,R,L) :- sc(SId,Sn,Id,R,L), p(Id,N,C),
?true6.
sc_a(SId,Sn,Id,R,L) :- sc(SId,Sn,Id,R,L), s(Id,Mj,Mi), Mj = cs,
?true7.
p_a(Id,N,C)
:- p(Id,N,C), s(Id,cs,Mi), sc(SId,Sn,Id,R,L), ?true8.
s_a(Id,Mj,Mi)
:- s(Id,Mj,Mi), p(Id,N,C), sc(SId,Sn,Id,R,L), ?true9.
sc_a(SId,Sn,Id,R,L) :- sc(SId,Sn,Id,R,L), s(Id,cs,Mi), p(Id,N,C), ?true10.
% Completeness check and the failure constraint
complete :- p_a(Id,Name,Country), s_a(Id,Mj,Mi), Mj ?= cs.
:- not complete.
[EXAMPLES]
negative: p(i,n,c). s(i,cs,mi).
positive: p(i,n,c). s(i,cs,mi). fk_holds(1).
positive: p(i,n,c). s(i,cs,mi). fk_holds(2).

Fig. 6: Core sketched encoding for the query-completeness use-case

2015), where an imperative program has a question mark instead of a constant and a programmer
provides a number of examples to find the right substitution for it. While sketching has been used
in imperative programming languages, it has – to the best of the authors’ knowledge – never been
applied to ASP and constraint programming. What is also new is that the sketched ASP is solved
using a standard ASP solver, i.e., ASP itself.
Second, there is a connection to the field of inductive (logic) programming (De Raedt, 2008;
Muggleton and De Raedt, 1994; Gulwani et al., 2015) as one induces programs from examples of their intended behaviour. Particularly interesting in this regard is also the work on metainterpretive learning (Muggleton et al., 2014, 2015) where a Prolog or Datalog program is learned
from a set of higher-order rules and examples. The higher-order rule act as a kind of template that
can be used to complete the program. However, meta-interpretive learning differs from SkASP
in that it induces full programs and pursues as other inductive logic programming approaches in
that it pursues a search- and a trace-based approach guided by generality, whereas SkASP using
a constraint solver (i.e., ASP itself) directly. Furthermore, the target is different in that ASPs are
learned (which include constraints) rather than Prolog or Datalog programs. On the other hand,
meta-interpretive learning also supports predicate invention.
There also exists interesting work in the intersection of ILP, program synthesis and ASP, e.g.
(Law et al., 2014), where an ASP program is learned from positive and negative examples, and
a set of modes, while minimizing a metric through a search process. The program, learned completely from scratch, is not necessarily the best program from the user’s point of view and may
limit the possibility to localize the uncertainty from the user’s knowledge of the problem.
Third, there is also work on constraint learning, where a number of systems such as CONACQ
(Bessiere et al., 2005, 2017) and QUACQ (Bessiere et al., 2013) learn a set of propositional constraints, and ModelSeeker (Beldiceanu and Simonis, 2012) learns global constraints governing
a particular set of examples. The subject has also been investigated in an inductive logic programming setting by (Lallouet et al., 2010). However, the idea in all these approaches is to learn
the complete specification of the constraint satisfaction problem from scratch, and hence, these
approaches do not take a debugging perspective. The present setting is probably more realistic
from a user perspective as it allows to use the knowledge that the user no doubt possesses about

Sketched Answer Set Programming

13

the underlying CSP problem, and also requires much less examples. On the other hand, SkASP
also makes, as other sketching approaches, the strong assumption that the intended target program is an instance of the sketched one. This may not always be true, for instance, when rules
are missing in the program. This is also an interesting issue for further research.
Fourth, our approach is related to the line of research in debugging of ASP (Gebser, Pührer,
Schaub, and Tompits, Gebser et al.; Oetsch et al., 2011). Unlike SkASP such debuggers can be
used to locate the bug, but typically do not provide help for fixing the bugs. On the other hand,
once the bug has been identified SkASP could be used to repair the bug by introducing a sketch
and a number of examples. The approach of Li et al. (2015), contrary to our approach, is based
on classical ILP techniques of generalization and specification and does not provide the freedom
to indicate uncertain parts of the program.
Finally, from the technical point of view our work bears certain technical similarities with
meta-interpretation in ASP (Eiter and Polleres, 2006), such as rule and decision materialization.
The purpose of their work is, however, different: they aim at synthesizing a new program of
higher complexity (ΣP2 ) given two programs of lower complexity (NP and Co-NP).
7 Discussion and Conclusions
Our contribution is four-fold: we have introduced the problem of sketched ASP; we have provided a sound and complete rewriting schema for sketched ASPs; we showed that the complexity
of the rewriting is the same as that of the existence of an AS; we have create a dataset of sketched
problems and evaluated our approach empirically demonstrating its efficiency and effectiveness.
User interaction is an interesting direction for future work, namely to suggest constraints and
examples. For the former, if we are not able to reject a negative example, we can construct a
constraint that would reject the negative examples and none of the positive examples. As for the
examples, if we have two solutions to a problem, we can generate an example discriminating
between them and ask user to clarify it, while this might not always be possible, since symmetric
assignments might lead to semantically identical programs. In practice, however, this might be
an important addition to simplify sketching for end users. Another interesting direction is to
incorporate preference handling into the ASP model using the extensions of ASP for preference
handling, such as asprin (Brewka et al., 2015).
References
B ELDICEANU , N. AND S IMONIS , H. 2012. A model seeker: Extracting global constraint models from
positive examples. In CP, pp. 141–157.
B ESSIERE , C., C OLETTA , R., H EBRARD , E., K ATSIRELOS , G., L AZAAR , N., NARODYTSKA , N., Q UIM PER , C., AND WALSH , T. 2013. Constraint acquisition via partial queries. In IJCAI, pp. 475–481.
B ESSIERE , C., C OLETTA , R., AND KORICHE , F. 2005. A sat-based version space algorithm for acquiring
constraint satisfaction problems. In ECML, pp. 23–34. Springer.
B ESSIERE , C., KORICHE , F., L AZAAR , N., AND O’S ULLIVAN , B. 2017. Constraint acquisition. Artif.
Intell. In Press.
B REWKA , G., D ELGRANDE , J., ROMERO , J., AND S CHAUB , T. 2015. Asprin: Customizing answer set
preferences without a headache. In AAAI, pp. 1467–1474. AAAI Press.
B RUYNOOGHE , M., B LOCKEEL , H., B OGAERTS , B., DE C AT, B., P OOTER , S. D., JANSEN , J.,
L ABARRE , A., R AMON , J., D ENECKER , M., AND V ERWER , S. 2013. Predicate logic as a modeling language: Modeling and solving some machine learning and data mining problems with IDP3.
CoRR abs/1309.6883.

14

Sergey Paramonov, Christian Bessiere, Anton Dries, Luc De Raedt

D E R AEDT , L. 2008. Logical and Relational Learning: From ILP to MRDM (Cognitive Technologies).
Springer-Verlag New York, Inc., Secaucus, NJ, USA.
E ITER , T., I ANNI , G., AND K RENNWALLNER , T. 2009. Reasoning web. semantic technologies for information systems. Chapter Answer Set Programming: A Primer, pp. 40–110.
E ITER , T. AND P OLLERES , A. 2006. Towards automated integration of guess and check programs in
answer set programming: a meta-interpreter and applications. TPLP 6, 1-2, 23–60.
G EBSER , M., K AMINSKI , R., K AUFMANN , B., AND S CHAUB , T. 2012. Answer Set Solving in Practice.
Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers.
G EBSER , M., P ÜHRER , J., S CHAUB , T., AND T OMPITS , H. A meta-programming technique for debugging
answer-set programs. In AAAI.
G ELFOND , M. AND L IFSCHITZ , V. 1988. The stable model semantics for logic programming. In
ICLP/SLP, Volume 88, pp. 1070–1080.
G ULWANI , S., H ERNANDEZ -O RALLO , J., K ITZELMANN , E., M UGGLETON , S. H., S CHMID , U., AND
Z ORN , B. 2015. Inductive programming meets the real world. Commun. ACM 58, 11, 90–99.
H ÖLLDOBLER , S. AND S CHWEIZER , L. 2014. Answer set programming and clasp a tutorial. In Young
Scientists International Workshop on Trends in Information Processing (YSIP), pp. 77.
J EON , J., Q IU , X., F OSTER , J. S., AND L EZAMA , A. S. 2015. Jsketch: sketching for java. In ESEC/FSE,
pp. 934–937.
L ALLOUET, A., L OPEZ , M., M ARTIN , L., AND V RAIN , C. 2010. On learning constraint problems. In
ICTAI, pp. 45–52.
L AW, M., RUSSO , A., AND B RODA , K. 2014. Inductive Learning of Answer Set Programs, pp. 311–325.
Springer International Publishing, Cham.
L EZAMA , A. S. 2009. The sketching approach to program synthesis. In APLAS, pp. 4–13.
L EZAMA , A. S. 2013. Program sketching. STTT 15, 475–495.
L I , T., VOS , M. D., PADGET, J., S ATOH , K., AND BALKE , T. 2015. Debugging ASP using ILP. In
Technical Communications ICLP Cork, Ireland.
L IFSCHITZ , V. 2008. What is answer set programming? AAAI.
M UGGLETON , S. AND D E R AEDT , L. 1994. Inductive logic programming: Theory and methods. Journal
of Logic Programming 19, 20, 629–679.
M UGGLETON , S. H., L IN , D., PAHLAVI , N., AND TAMADDONI -N EZHAD , A. 2014. Meta-interpretive
learning: application to grammatical inference. Machine Learning 94, 1, 25–49.
M UGGLETON , S. H., L IN , D., AND TAMADDONI -N EZHAD , A. 2015. Meta-interpretive learning of
higher-order dyadic datalog: predicate invention revisited. Machine Learning 100, 1, 49–73.
N UTT, W., PARAMONOV, S., AND S AVKOVIC , O. 2013. An ASP approach to query completeness reasoning. TPLP 13, 4-5-Online-Supplement.
N UTT, W., PARAMONOV, S., AND S AVKOVIC , O. 2015. Implementing query completeness reasoning. In
CIKM, pp. 733–742.
O ETSCH , J., P ÜHRER , J., AND T OMPITS , H. 2011. Stepping through an Answer-Set Program, pp. 134–
147. Springer Berlin Heidelberg.
Ö ZG ÜR , A. 2015.
CSPLib problem 110: Peaceably co-existing armies of queens.
http://www.csplib.org/Problems/prob110.
R AZNIEWSKI , S. AND N UTT, W. 2011. Completeness of queries over incomplete databases. PVLDB 4, 11,
749–760.
ROSSI , F., VAN B EEK , P., AND WALSH , T. (Eds.) 2006. Handbook of Constraint Programming. Foundations of Artificial Intelligence. Elsevier.
S AVKOVIC , O., M IRZA , P., PARAMONOV, S., AND N UTT, W. 2012. MAGIK: managing completeness of
data. In CIKM, pp. 2725–2727.

Appendix A Dataset Description
In Table A 1, we provide an overview of the dataset and its properties, such the number of
sketched variable in each problem and the number of rules, other columns denote the number of
particular type of sketched variables, e.g., “# ?not” indicates how many atom with the sketched

15

Sketched Answer Set Programming
Problem
Graph Clique
3D Matching
Graph Coloring
Domination Set
Exact Cover
Sudoku
B&W Queens
Hitting Set
Hamiltonian Cycle
Feedback Arc Set
Latin Square
Edge Domination
Frequency Assignment
Set Packing
Clique Cover
Feedback Vertex Set
Edge Coloring
Set Splitting
N Queens
Vertex Cover
Subgraph Isomorphism

# Sketched variables

# ?=

# ?+

# ?not

# ?p

# Rules

3
3
7
3
7
5
5
3
3
4
4
3
5
4
4
5
3
5
6
3
5

1
3
4
0
2
4
3
0
0
0
4
0
3
2
3
0
3
2
4
0
2

0
0
0
0
0
0
2
0
0
0
0
0
2
0
0
0
0
0
2
0
0

0
0
0
1
1
1
0
1
1
2
0
1
0
0
1
5
0
1
0
1
1

2
0
3
2
4
0
0
2
2
2
0
2
0
2
0
0
0
2
0
2
2

4
1
2
5
3
4
3
2
3
3
2
5
3
1
3
3
3
3
3
4
4

Table A 1: Dataset summary
negation are in the program. Of course, one can introduce a different set of sketched variables
for each problem but to give a more complete picture of the experimental settings we describe
the dataset as it has been used in the experiments.

