The development of answer-set programs often involves domain experts without a background in logic programming. In such situations, it would be beneficial to translate programs into a form which is easier to understand and closer to natural language. Since the structure of a program determines to a great extent how a program should be explained in a clear and comprehensible way, as a first step towards a natural-language representation of answer-set programs, in this paper, we introduce methods for analysing the structure of disjunctive non-ground answer-set programs. In particular, as most programs follow the generate-define-test paradigm, we introduce formal definitions to characterise the respective generate, define, and test parts of a program. Thereby, we define the non-deterministic core of a program, effectively determining the program's active solution-space generators, following ideas of the weakly perfect model semantics as introduced by Przymusinska and Przymusinski, and we prove that our definitions fulfil desirable properties. Moreover, we also provide an implementation of a tool, using a metaprogramming approach, which classifies the rules of a given program according to our definitions. Finally, we propose an algorithm that, based on our generate-define-test classification, computes the order in which the rules of a program should be explained when translated into natural language.
BENJAMIN KIESL,1 PETER SCHÜLLER,2 and HANS TOMPITS1
Answer-set programming (ASP) has proven to be a viable tool for knowledge representation, reasoning, and solving complex search problems. In many cases, the process of developing answer-set programs involves domain experts, i.e., persons with a detailed knowledge of some certain field of application but often without This work has been supported by the Austrian Science Fund (FWF) under project W1255-N23 and by the Scientific and Technological Research Council of Turkey (TUBITAK) under grant 114E777. a background in ASP. Such experts provide their know-how of a specific topic to software developers who are then concerned with encoding this expertise into answer-set programs. In such a context, arguably the software-engineering process for answer-set programs involving non-ASP experts could be eased if representations of the programs and their output in a form which is closer to natural language would be available.
Since the structure of a program determines to a great extent how a program
should be explained in a clear and understandable way, as a first step towards
realising natural-language representations of answer-set programs, we introduce in
this paper methods for analysing the structure of disjunctive non-ground
answerset programs. We note that work addressing representations in the other direction,
i.e., from natural language to ASP, has been discussed in the literature, e.g., by
A key structural feature of most answer-set programs is that they adhere to
the so-called generate-define-test paradigm which was informally introduced by
For a natural definition of the non-deterministic generate part of a program, it
is necessary to identify cases in which default negation leads to non-deterministic
behaviour. From a result of
Based on ideas underlying the procedure for the computation of the
weaklyperfect model of a logic program
We also present an implementation of a tool, based on a metaprogramming approach, which classifies the rules of a given program according to our definitions. Finally, we propose an algorithm that makes use of our generate-define-test classification to compute a specific order for explaining the rules of a program in natural language.
We deal with logic programs which are finite sets of rules of form
L1 _ : : : _ Lk
Lk+1; : : : ; Lm ; not Lm+1; : : : ; not Ln ; (1) where L1; : : : ; Ln are literals, i.e., atoms from some (implicitly given) functionfree first-order language L, possibly preceded by the strong-negation symbol “ :”. Literals which are possibly preceded by the default-negation symbol “ not” are called default literals. Given a rule r as above, we define head(r ) = fL1; : : : ; Lk g, body+(r ) = fLk+1; : : : ; Lm g, and body (r ) = fLm+1; : : : ; Ln g. The elements of head(r ) are referred to as the head literals of r , while the elements of body+(r ) and body (r ) are respectively referred to as the positive and negative body literals of r . Moreover, we also define body(r ) = body+(r ) [ body (r ). We call a rule of form (1) disjunctive if k > 1, a fact if body(r ) = ;, and a constraint if head(r ) = ;. A program is extended if it contains no disjunctive rules, normal if it contains neither disjunctions nor strong negations, and positive if for every r 2 , body (r ) = ;. Given a rule or program e, we denote by at(e) (resp., lit(e)) the set of atoms (resp., literals) in e.
The grounding of a logic program relative to its Herbrand universe HU ( ) is
defined as usual and denoted by grd( ). Let M be a set of ground (variable-free)
literals. M satisfies a rule r if body+(r ) M and body (r )\M = ; only if head(r )\
M 6= ;. Furthermore, M is closed under a program if M satisfies all rules in
, and M is logically closed if it is consistent (i.e., for no literal L 2 M we have
fL; :Lg M) or contains all literals. The reduct, M, of relative to M
The dependency graph, DG( ), of a program
Given a program and literals A and B , A depends positively (resp., depends negatively ) on B if DG( ) contains a positive (resp., negative) path from B to A. Moreover, A depends on B if A depends positively or negatively on B .
The rule graph, RG( ), of a program
A normal logic program is stratified if there exists a mapping f assigning
each predicate symbol a natural number such that, for every rule r 2 and every
predicate P1 and P2, (i) if P1 occurs in head(r ) and P2 occurs in body+(r ) then
f (P1) f (P2), and (ii) if P1 occurs in head(r ) and P2 occurs in body (r ) then
f (P1) > f (P2). Let 0 be the program obtained from grd( ) by replacing every atom
with a corresponding propositional predicate symbol. Then, is locally stratified
if 0 is stratified
In this section, we introduce formal definitions of the generate, define, and test parts of an answer-set program. Furthermore, we also sketch a metaprogram which classifies the rules of a given answer-set program according to our definitions.
As already noted in Section 1, the generate part should contain those rules which cause non-determinism in the sense that they generate multiple answer-set candidates. Disjunctive rules and negative cycles are obvious sources of such nondeterminism, but, although even negative cycles are in the absence of disjunction necessary for the creation of multiple answer sets, they are not sufficient. Consider, for illustration, the program 1, consisting of the facts n(1), n(2), and succ(1; 2), together with the following rule which, intuitively, chooses every second element of the set n: choose(Y ) n(X ); n(Y ); succ(X ; Y ); not choose(X ). (2) (3) (4) (5) (6) The grounding of stances of (2): choose(1) choose(1) Rules (4) and (5) are involved in an even negative cycle with literals choose(1) and choose(2). Still, 1 has the unique answer set fn(1); n(2); succ(1; 2); choose(2)g. Intuitively, the negative cycle does not become active in the sense that the body atom succ(2; 1) in Rule (4) cannot be contained in an answer set of 1. Modern grounders automatically eliminate a rule like (4) from the grounding of 1 but there are more intricate cases where grounders are not able to remove such negative cycles. 1 contains, additionally to the facts, the following ground inn(1); n(1); succ(1; 1); not choose(1); n(2); n(1); succ(2; 1); not choose(2); n(1); n(2); succ(1; 2); not choose(1); n(2); n(2); succ(2; 2); not choose(2).
The observation that in many cases negative cycles do not become active has
already been made by
We next use ideas behind the weakly-perfect-model semantics to define the nondeterministic core (short, nd-core) of a program. The nd-core is obtained by removing certain rules and literals such that negative cycles which cannot become active are eliminated. We begin with the definition of weakly minimal literals.
A literal L 2 lit(grd( )) is weakly minimal if it does not depend negatively on other literals and if it does not depend on a literal in the head of a disjunctive rule.
The deterministic bottom-stratum, dbs( ), of is the set of all weakly-minimal literals which do not occur in the heads of disjunctive rules. Furthermore, the deterministic bottom-layer, dbl( ), of is the set fr 2 grd( ) j head(r ) dbs( )g. The deterministic bottom-layer of a program can be seen as the positive deterministic portion of a program since it is a non-disjunctive positive program which clearly has a unique answer set.
Let 2 consist of the set of facts fn(1); n(2); succ(1; 2)g and the following rules: chooseEven; n(X ); n(Y ); succ(X ; Y ); not choose(X ); chooseAll; n(X ); not chooseAll; not chooseEven. (7) (8) (9) (10) (11) (12) (13) (14) (15) (16) 2 has two answer sets: one in which choose(n) is true for every number n and one in which choose(n) is only true for even n. The grounding of 2 contains the facts together with Rules (9) and (10), and the following instances of (7) and (8): chooseEven; n(1); n(1); succ(1; 1); not choose(1); chooseEven; n(2); n(1); succ(2; 1); not choose(2); chooseEven; n(1); n(2); succ(1; 2); not choose(1); chooseEven; n(2); n(2); succ(2; 2); not choose(2); chooseAll; n(1); chooseAll; n(2).
Then, the deterministic bottom-stratum of grd( 2) is dbs(grd( 2)) = fn(1); n(2); succ(1; 1); succ(1; 2); succ(2; 1); succ(2; 2)g, and thus the deterministic bottom-layer is dbl(grd( 2)) = fsucc(1; 2) ; n(2) ; n(1) g. For defining the nd-core of a program we repeatedly apply the transformation given in Definition 3 until a fixed-point is reached. The intuitive idea behind this transformation is to first evaluate the deterministic positive portion of the program, identified by its deterministic bottom-layer. The deterministic bottom-layer, as well as further rules whose bodies can never become satisfied or which are redundant, are then removed. Additionally, default literals that are satisfied by the unique answer set of the deterministic bottom-layer are removed from the remaining rules. This eliminates certain negative cycles that have a deterministic effect.
Let be a ground logic program and M the unique answer set of dbl( ). Then, ( ) is the program obtained from by (i) removing all rules which contain a negative body literal N such that N 2 M, a positive body literal P such that P 2 dbs( ) n M, or a head literal H with H 2 M, (ii) removing those body default literals such that P 2 M for positive body literals
P or N 2 dbs( ) n M for negative body literals N , and (iii) removing all non-facts whose heads appear as facts in the program. The removal of non-facts whose heads appear as facts is important for programs like 3 = fa not b; b not a; a g. Here, it allows to remove the first rule although dbs( 3) = ; and so ( 3) has, in contrast to 3, no negative cycles.
Based on the operator , we can now define the non-deterministic core of a (possibly non-ground) program, intuitively obtained by partially evaluating its deterministic portion (which may involve negative default literals) and transforming the program accordingly.
As a preparatory step, let 0( ) = and i+1( ) = ( i ( )), for i 2 N+. Clearly, the application of to a ground logic program removes from all the literals of dbs( ) and does not add any literals. Hence, there is an i such that either (a) i ( ) = ; and thus i+1( ) = ;, or (b) i+1( ) is non-empty and does not differ from i ( ), as dbs( i ( )) = ;, and i ( ) does not contain any non-facts whose heads occur as facts. Thus, the following holds:
For every ground logic program k ( ), for each k i0. , there is a smallest number i0 such that i0 ( ) =
1( ) for i0 ( ) with i0 as in Theorem 1. We then define:
The non-deterministic core (or nd-core) of a program is given by 1(grd( )).
Let = grd( 3), where 3 is the program from the above. In Example 1, we already identified that dbl( ) = fn(1) ; n(2) ; succ(1; 2) g. Its unique answer set is M = fn(1); n(2); succ(1; 2)g. Now, when computing ( ), Rules (11), (12), and (14) are removed since their body literals succ(1; 1), succ(2; 1), and succ(2; 2) are contained in dbs( ) n M. As well, the facts succ(1; 2) , n(1) , and n(2) are removed since their heads are contained in M. Finally, the body literals n(1), n(2), and succ(1; 2) are removed from the remaining rules since they are contained in M. We thus obtain 1( ) = ( ) as follows: choose(2) Since 1( ) does not contain any weakly-minimal literals, we have that dbs( 1( ))= ;. Therefore, 2( ) = 1( ), and so 1( ) is already the nd-core of 3. In this example, only one application of was necessary for computing the nd-core of 3. But this is not always the case. In fact, the number of computation steps cannot be bounded by a constant, as stated by the following theorem:
For every n 2 N, there is a ground program n such that 1( n ) 6= n 1( n ).
Having the nd-core of a program at our disposal, we can now define the generate, define, and test parts. In the following, an instance of a rule r refers to a rule which was obtained from r by grounding it and which has possibly been modified by .
Let be a logic program. Then, (i) the generate part of consists of all rules which are disjunctive or which have instances that are involved in even negative cycles within the dependency graph of the nd-core of , (ii) the test part of consists of all rules which are not in the generate part and which are either constraints or which have instances that are involved in (odd) negative cycles within the dependency graph of the nd-core of , and (iii) the define part of consists of all rules which are neither in the generate part nor in the test part.
Rules of the generate, define, and test part are referred to as generating, defining, and testing rules, respectively.
Note that we are explicitly speaking of instances of (non-ground) rules which are involved in negative cycles and not of rules whose head literals or predicates are contained in a negative cycle. Note also that facts are contained in the define part but it would be straightforward to define a separate part for them.
Also, often in non-ground ASP, one deals with uniform problem encodings, in which a program is detached from the set of facts providing the input of the program. From a database point of view, the program is the intensional database (IDB) whilst the facts constitute the extensional database (EDB). When trying to analyse the structure of such a uniform encoding , the analysis of can be done by computing the nd-core of [ f , where f consists of input facts comprising instances of atoms of all extensional predicates of .
For the program
2, the generate part consists of the rules chooseEven not chooseAll and chooseAll not chooseEven, while the define part contains the facts together with the following rules: chooseEven; n(X ); n(Y ); succ(X ; Y ); not choose(X ); chooseAll; n(X ). (22) (23)
In the dependency graph of 2, instances of (22) are involved in negative cycles with an even number of negative edges as well as in negative cycles with an odd number of negative edges. But, contrary to common intuition, these cycles neither cause the creation of multiple (candidate) answer sets nor do they eliminate them. Hence, (22) is a defining rule and not a generating or a testing rule. In fact, (22) would even be a defining rule if predicate succ would not be defined by facts but by an equivalent set of rules including default negation.
Next, we discuss some properties of the above definitions.
The nd-core of every weakly stratified program, and thus of every (locally) stratified program, is empty.
The generate part of every weakly stratified program, and thus of every (locally) stratified program, is empty.
The following theorem expresses that a non-deterministic behaviour of a program always has its origin in the generate part.
A program with an empty generate part has at most one answer set. Note that the converse of this statement does not hold since the generate part can create multiple answer-set candidates which are all eliminated by the test part.
In concluding this section, we remark that we implemented a tool which classifies logic programs into its generate, define, and test parts according to our definitions. The tool is implemented in Java and performs the computation of the nd-core and the identification of rules which are involved within its negative cycles by means of an ASP metaprogramming approach, using an answer-set program consisting of the following modules: (i) reify , representing the input program as a set of facts, (ii) (iii) (iv) (v) dependency , defining the dependency notions, bottomlayer , identifying the deterministic bottom-stratum and the corresponding deterministic bottom-layer, nd-core , encoding the operator and computing the nd-core, and cycle , identifying rules which are involved in even and odd negative cycles within the dependency graph.
Since the whole metaprogram consists of more than 100 rules we do not list it here. It is available at www.kr.tuwien.ac.at/staff/kiesl/gdt_classification.lp.
For obtaining an understandable explanation of an answer-set program, the order in which the rules are explained is crucial. One way to obtain arguably useful explanations is to start with generating rules and then continue by explaining how the predicates of the generate part are constrained by rules from the test part, thereby also taking the involved defining rules into account. In what follows, we discuss a method for assigning an explanation order on rules which also copes in an intuitive way with testing rules that constrain several generating rules.
Assume that we want to assign colours to the vertices of a graph such that every vertex is either red, blue, or has no colour at all. Furthermore, some of the vertices are not allowed to be either red or blue, represented by predicates must_not_be_red and must_not_be_blue. A possible encoding is the following program 4: There are two generating rules, (24) and (25). Among the three constraints, (26) is only related to literals generated by (24), (27) is only related to those generated by (25), and (28) is related to literals that are generated by both generating rules.
We believe that a useful explanation of the whole program is as follows: we start by explaining the generating rule (24) together with its corresponding constraint (26); after that we explain (25) together with (27), and at the end we mention (28) which constrains both generating rules. A natural-language explanation realising this order could be as follows: 1. For any vertex, choose whether it is red or not [Rule (24)] such that no vertex which must not be red is red [Rule (26)].
which must not be blue is blue [Rule (27)].
blue [Rule (28)]. vertex(X ); red(X ); must_not_be_red(X )
vertex(X ); blue(X ); must_not_be_blue(X ) vertex(X ); red(X ); blue(X )
To formalise the intuition behind this order, we make use of the strongly-connected components (SCCs) of the rule graph RG( ) of a program . Given a rule r 2 we denote by SCC(r ) the SCC of RG( ) containing r . We call the graph obtained by collapsing SCCs of RG( ) the reduction graph of RG( ). An SCC of RG( ) is maximal if it does not have an outgoing edge within the reduction graph of RG( ).
A rule of a program
is maximal if it is contained in a maximal SCC of RG( ).
A generating rule rG of a program is maximal if in RG( ) (i) no generating rule in SCC(rG ) has more outgoing edges than rG and (ii) there is no directed path from rG to a generating rule in a different SCC of RG( ).
The intuition behind this definition is to give priority to explaining generating rules that are most influential in the program (according to outgoing paths) and that are nearest to testing rules and definitions.
We next formalise that testing rules can be associated with certain rules.
Given a logic program , let rT 2 be a testing rule and r 2 a rule. Then, r is constrained by rT if there is a directed path from r to rT in RG( ), otherwise r is unconstrained by rT .
Note that testing rules are trivially constrained by themselves.
Figure 1 depicts the rule graph of 4. According to our definitions, (26) constrains only (24), (27) constrains only (25), and (28) constrains both (24) and (25). All three constraints induce maximal components and thus they are maximal rules. Both generating rules (24) and (25) are maximal ones.
Algorithm 1 computes an order for explaining rules of a given program. Intuitively, rules are explained in the order they are visited during a depth-first traversal of the rule graph, starting from maximal rules and maximal generating rules. During the traversal, rules which are in the same SCC are preferred. Additionally, as soon as all rules from which a generating rule rG is reachable have been visited, testing rules which constrain rG are explained. Step (a) first explains unconstrained maximal rules, then maximal generating rules, and finally arbitrary maximal rules.
Algorithm 1 always terminates and assigns a unique number to each rule. input : rule graph G output: order in which the rules are explained, defined by order let sameSCC and otherSCC be stacks let i := 1 while G contains unlabelled rules do if otherSCC is empty then let r be an unlabelled rule according to the following priority: - first choose unconstrained maximal rules, - then choose maximal generating rules, - then choose maximal rules.
push(sameSCC; r ) while sameSCC or otherSCC is not empty do if sameSCC is not empty then
let r := pop(sameSCC) else
let r := pop(otherSCC) if r is not labelled then let order(r ) := i // now we consider r to be labelled let i := i + 1 // iterate in the same order as the r 0 occur in the body of r for all edges (r 0; r ) in G do if r 0 is in the same SCC as r then
push(sameSCC; r 0) else
push(otherSCC; r 0) (b) let l be the list of unlabelled testing rules order l by the number of generating rules they constrain, descending for c in l do if all generating rules constrained by c are labelled then
push(otherSCC; c)
Algorithm 1: Computes the order in which rules are explained.
Example 6 (continued )
4 does not contain unconstrained rules, so in Step (a) of Algorithm 1 we choose one of the generating rules, say (24). It has no incoming edges but after labelling it with 1, all rules constrained by (26) are labelled, hence (26) is pushed in Step (b) and labelled with 2. Subsequently, the next unlabelled maximal generating rule is chosen in (a), viz. Rule (25), and labelled with 3. Then, (27) is pushed in (b) and labelled with 4 since all rules which are constrained by (27) were labelled. Finally, (28) is pushed in (b) since now both rules which it constrains have been labelled. Note that (28) is visited after (27) because (28) constrains more generating rules than (27). We end up with the following order: 1: 2: blue(X ) _ :blue(X ) vertex(X ), vertex(X ), vertex(X ); red(X ); must_not_be_red(X ), 4: 5: vertex(X ); blue(X ); must_not_be_blue(X ), vertex(X ); red(X ); blue(X ), which is exactly the order we wanted at the beginning of this section.
We introduced methods for structural analysis of non-ground disjunctive answer-set programs. In particular, we introduced formal definitions for the generate, define, and test parts of a program. In order to arrive at natural definitions, we first defined the non-deterministic core of a program, which is obtained by eliminating deterministically determined rules and literals. This has the potential to eliminate those negative cycles that cannot become active and thus should not be considered in the generate or test part. We then defined generating rules to be disjunctive rules as well as rules having instances that are involved in the non-deterministic core’s even negative cycles. From the remaining rules, we defined the test part to contain constraints and rules which have instances that are involved in the core’s odd negative cycles, and all remaining rules are then considered to represent definitions.
We implemented a tool based on metaprogramming which classifies rules in an answer-set program accordingly. The aim of this tool is to apply it for translating programs into (controlled) natural language, however by itself this tool can be useful for developers to quicker gain an understanding of a given program. Based on our definitions of generate-define-test, we introduced an algorithm which computes an order for translating rules of a program into CNL. We believe we found criteria that yield a clear and understandable explanation of the overall program.
Our approach differs from justification-based methods (
As future work, we plan to automatically realise a translation of answer-set programs into controlled natural language. Moreover, we want to extend our methods to programs of broader syntactic classes, e.g., classes with language features like choice constructs or aggregate relations.
We also plan to investigate how our definition of the non-deterministic core
relates to program normal forms as introduced by Brass et al. (1996; 2001) for the
computation of the well-founded semantics. Note that the normal forms introduced
by
We think that optimisation of non-ground logic programs can profit from our
work, e.g.,