In this paper, we propose a formalization of the features that a graph representation of logic programs under the answer set semantics should in our opinion exhibit in order to be a satisfactory and useful representation formalism. We introduce a concept of isomorphism between a program and the corresponding graph. We show the importance of isomorphism for program analysis and we compare different graph representations w.r.t. isomorphism.
Answer Set Programming (ASP) [
With the growth of practical real-world ASP applications, the need is arising of writing programs with a complicated structure, and of composing existing programs into larger ones. Guidelines should be provided to programmers and system developers, in order to write consistent (or, sometimes, purposedly inconsistent) programs, and to combine them.
These guidelines should be based upon some kind of representation of logic programs. We believe that the properties of a good representation are at least the following: (i) the relationship between the program and its representation is clearly understandable; (ii) it is easy to shift back and forth from the program to the representation, so that a change in the program reflects into a change in the representation, and vice versa; (iii) it is possible to use the representation for developing techniques to define significant subprograms, study their interactions and determine which program parts can influence specific, critical points, and thus influence relevant program properties.
Graph representations are in our opinion good candidates. In fact, graphs are simple and understandable. Graph-theoretic structures are able to represent properties of programs. Known properties of graphs can help improve the understanding of structural properties of the programs themselves.
In this paper we propose a formalization of the features that a graph representation of logic programs should in our opinion exhibit in order to be a satisfactory and useful representation formalism. We introduce a concept of isomorphism between a program and the corresponding graph, and we show that isomorphism is possible only if a graph representation formalism is able to distinguish the cycles occurring in the program, and the different connections among them.
We discuss isomorphism w.r.t. three graph representations: the traditional
Dependency Graph DG, the Extended Dependency Graph EDG [
The paper is organized as follows. In Section 2 we discuss properties of graph representations and we introduce isomorphic graph representations, and their relationship to cycles. In Section 3 we motivate these representations by showing how cycles occurring in a program affect the existence and number of answer sets. In Sections 4, 5 and 6 we examine various graph representations to establish their properties. Finally, Section 7 concludes the paper. The reader can find an introduction to ASP in Appendix A, and some basic definitions about graphs in Appendix B. 2
The main property of programs one wants in the first place to study under the answer
set semantics is consistency, i.e., the existence (and the number) of answer sets. In
general, one has to compute and often examine the answer sets (e.g., in order to check
whether some desired conclusion has been actually reached, or if a soft constraint is
satisfied). In some situations, for instance for debugging a program or for trying to
combine different program components, one may want to be able to investigate the
program structure, in order to understand which parts influence which others, and then
what ensures consistency, and what can spoil it [
As it is well-known, the Dependency Graph is not a satisfactory representation for logic programs under these respects, as shown by the following example. Example 1. Consider the following programs 1, 2 and 3 (from left to right): p ← not p; not e: p ← not p: p ← not p; not e: a ← not b: p ← not e: a ← not b: b ← not a: a ← not b: b ← not a: e ← not f: b ← not a: e ← not f: f ← not h: e ← not f: f ← not h: h ← not e: f ← not h: h ← not e; not a: h ← not a: h ← not e; not a: It is easy to see that the dependency graphs of the three programs coincide. Namely, the DG of the three programs is the leftmost graph of Figure 1. However, 1 has answer set {b; e; h} while instead 2 has answer set {a; f; p} and 3 has no answer sets at all, i.e. it is inconsistent.
Inconsistency may arise only because of odd cycles: in fact, call-consistent
programs [
However, the different connections between the odd cycles and the rest of the program, that cannot be seen on the DG, influence the existence and the number of answer sets.
Moreover, based on the DG it is impossible to make predictions about what happens in case of modifications. For instance, if adding fact e, the following happens: (i) program 1 remains consistent, with the two answer sets {b; e; h} and {a; e; f }; (ii) 2 becomes inconsistent; (iii) 3 becomes consistent, with the two answer sets {b; e; f } and {a; e; f }.
Since we are interested in the syntactic structure of programs, let us characterize those programs that have the same structure, but different names for the atoms occurring in them.
Definition 1. Let P be a logic program with Herbrand base BP = {a1; a2; : : : ; ah}, and let BP′ be a set of atoms with the same cardinality as BP . A renaming is an injective and surjective function from BP to BP′ , that can be denoted as a set {(a1; a′1); (a2; a′2); : : : ; (ah; a′h)} where ai ̸= aj implies a′i ̸= a′j , while for some k we may have ak = a′k. can be applied to P , thus obtaining a new program P ′ = P , by replacing every occurrence of ai by a′i.
Definition 2. Two logic programs P1 and P2 are renaming-equivalent if there exists a renaming from BP1 to BP2 such that P2 = P1 .
Let GF be any graph representation formalism (for instance the DG). By G ∈ GF we mean a graph G which can be constructed for some program according to GF . By GF (P) we mean the graph which represents program P according to GF . The following is a straightforward property of any graph representation.
Definition 3. A graph representation formalism GF is acceptable if for every logic program P , GF (P ) is unique.
A stronger requirement is that, given a graph, we can reconstruct the program that is represented by this graph, or at least a program, if there is more than one choice. This requirement is related to the usefulness of the representation as a software engineering tool: given a program, one can determine how it is represented; given a graph, one can guess which kind of program it represents.
Definition 4. A graph representation formalism GF is adequate if for every graph G ∈ GF , it is possible to construct from G a logic program P such that G = GF (P).
We may expect that two programs which are renaming-equivalent are represented by graphs which have the same structure. Instead, it is reasonable to expect that different programs have different representations.
Definition 5. An adequate graph representation formalism GF is unambiguous if for every two programs P1 and P2 which are not renaming-equivalent, we have that, apart from the labeling of vertices (if any), GF (P1) ̸= GF (P2).
For any graph representation formalism GF which is acceptable, adequate and unambiguous, we say that GF (P) is isomorphic to P . In fact, P can uniquely be determined from GF (P). More generally, we will say that the representation GF is isomorphic to logic programs. For short, we say that GF is an isomorphic graph representation.
Clearly, the Dependency Graph representation formalism is acceptable and adequate, but it is not unambiguous. In the example above in fact, it is impossible to say from the graph which of the three programs is being represented. Consequently, on the basis of the graph it is impossible to characterize consistency under the answer set semantics: we do not know from the graph whether the program under consideration has answer sets, and it is impossible to find these answer sets, and to predict whether they will change after updates. 3
An active handle gives a truth value to an atom involved in a cycle. Consequently, the truth value of all the other atoms of the cycle follows without contradictions. A necessary condition for consistency is that every odd cycle has at least one handle. This condition is not sufficient, since two handles can be in conflict, in the sense that they cannot be active simultaneously. For instance, take program fragment {v ← not v; not w; t ← not t; t ← not w}: there are two odd cycles, one involving v with AND handle not w, and the other one involving t with OR handle not w. Since the same condition not w occurs in two handles of different kind, they cannot be simultaneously active, and therefore the cycle, and the overall program, will be inconsistent. Whenever we have an even cycle without handles (unconstrained even cycle) we can choose any of the two answer sets of the corresponding program fragment in order to form an answer set of the overall program. For instance, for even cycle a ← not b; b ← not a any of the two answer sets {a}; {b} can be selected.
In [
The Extended Dependency Graph (EDG) has been introduced in [
V:2 vertices For each atom ai in that does not occur in the head of any rule there is a vertex ai(0).
E:1 edges For each c(jl) ∈ V , there is an edge ⟨c(jl); ai(k); +⟩, if and only if cj appears as a positive condition in the k-th rule defining ai.
E:2 edges For each c(jl) ∈ V , there is an edge ⟨c(jl); ai(k); −⟩, if and only if not cj appears as a negative condition in the k-th rule defining ai. to an edge ⟨c(jl); ai(k); −⟩.
The EDG for negative programs can be seen as a shortcut of the EDG for general programs, where each edge ⟨c(jl); ai(k)⟩ is implicitly labeled with “−”, i.e., corresponds
The definition of EDG extends that of DG in the sense that for programs where atoms are defined by at most one rule the two coincide. Consider in Figure 1 the EDGs of the programs in Example 1 (where h(1), h(2), p(1), p(2) are indicated as h, h′, p, p′ respectively, and all edges are implicitly labeled with ’−’).
a ?nb -Ænf
a Æ6
Æ6 h Æn a ?nb Æ- nf
On the EDGs, we clearly see the cycles, and also the handles. Consider EDG( 1) (center): rule {f ← not h:} is represented by the two edges ⟨h; f ⟩ and ⟨h′; f ⟩, since truth of h may depend on any of its defining rules; the second rule for h is auxiliary to the cycle, and corresponds to an OR handle. Therefore, we can see on the EDG that the cycle has an OR handle because the edge incoming into h′ originates in a duplication of one of the atoms of the cycle. In the same graph, edge ⟨e; p⟩ represents instead an AN D handle. In fact, we can see on the EDG that the cycle has an AND handle because there is an incoming edge into that cycle, originated in a duplication of an atom not belonging to the cycle itself. The even cycle involving a and b has no incoming edges and then it is unconstrained.
In general: given program , a cycle in corresponds to a cycle in EDG( ). On the EDG: (1) An AND handle for a cycle C relative to atom occurring in C is represented by an edge incoming into (additional condition of the rule defining ). Atom (and cycle C) may have either none or one or several AND handles. (2) An OR handle for a cycle C relative to atom occurring in C is represented by a sibling node of (additional rule defining ). More precisely, if C actually includes vertex i, another vertex j j ̸= i is also present in the EDG. Atom (and cycle C) may have either none or one or several OR handles.
It is proved in [
An important graph representation of negative logic programs is the Rule Graph (RG)
introduced in [
The rule graph allows useful conditions about existence of answer sets to be obtained, corresponding to formal properties coming from graph theory. In particular, answer sets correspond to kernels of the RG.
Notice that merging rules with the same head is an essential feature of the approach, which leads to increased ambiguity with respect to the original program. Take for instance the program: l1: a ← not b: l2 c ← not b: l3: b ← not a: l4: b ← not c: l5: c ← not a:
The reduced version is r1: a; c ← not b: r2: b; c ← not a: r3: b ← not c:
The kernels of the rule graph of the reduced version are two, namely r1 and r3. From the first one, going back to the reduced program one gets a stable model as the body of the corresponding rule, i.e., {b}. From the second one, again by taking the body of the corresponding rule, you get the stable model {c}. If, by abuse of notation, one draws the rule graph of the original program, no kernels are found.
For this reason, the RG and the EDG can be compared only on reduced programs, or, equivalently, on programs where all rules have different bodies. On this class of graphs, the RG and the EDG have the same structure, but with the important difference that vertices are labeled not with the name of the rules, but with (instances of) atoms. In particular, whenever there is only one atom in the body of each rule, this does not make any real difference, since the head of a rule being in the body of another collapses into the dependency between the two atoms. The difference instead exists and has a relevance whenever there are more atoms in the body of rules: in this case, the RG does not distinguish whether atoms in the body are one or more, and which one is the particular atom that is in common between two rules. Then, the RG cannot distinguish between AND and OR handles, and consequently it cannot be an isomorphic graph representation formalism.
In fact, below we exhibit two different programs, which are not renamingequivalent, and have both different answer sets and different EDGs, but the same RG.
Let 1 be: r1: a ← not b: r2: b ← not a: r3: g ← not g; not f: r4: f ← not q: r5: q ← not q; not a:
The unique answer set of 1 is {a; f }. In fact, not f is the unique AND handle for the odd cycle involving g. Then f must be true, and its truth is guaranteed by the truth of a, where not a is the unique AND handle of the odd cycle involving q. Consequently q is false.
Let 2 be: r1: a ← not b: r2: b ← not a: r3: g ← not g: r4: g ← not q: r5: q ← not q; not a:
The unique answer set of 2 is {a; g}. Again a must be true, since not a is the unique AND handle of the odd cycle involving q, which becomes false. In this program however, not q is the unique OR handle of the odd cycle involving g. The handle is thus active, and g is true.
The two programs have the same RG, shown in Figure 2.
r1 r5 r2 r4
r3
This is because in both cases we have that: the head of rule r4 is in the body of rule r3; the head of rule r5 is in the body of rule r4; atom a, which is the head of rule r1, is in the body of rule r5.
We can instantiate the general argument performed in the proof of Theorem 1 for the RG. (i) The RG is an adequate representation formalism if one guesses the Herbrand base of a program corresponding to the graph; many guesses are possible, the simplest one being to assign a different atom as the head of each different rule; other guesses are of course possible, where different rules have the same head. (ii) as a consequence of not being able to tell the heads of the rules, the RG as a representation formalism is not unambiguous: in fact, it is impossible to distinguish between 1 and 2 on the basis of the rule graph; Since 1 and 2 are reduced programs, it is moreover impossible to get back to the original programs. (iii) consequently, the RG is not an isomorphic graph representation formalism.
Then, in our opinion it would not be easy to define an interactive programming methodology on the basis of the rule graph, since it does not graphically distinguish among cases which are semantically very different.
This does not mean that the RG is not useful: on the contrary, it can be an effective
program analysis tool. In fact, in [
The Rule Graph RG has been extended in [
– The Body-Head Graph has bodies and heads as vertices, and: an edge (B; h) from each body B ∈ Body(P ) and the head h ∈ Head(P ) of each rule where B occurs; a positive edge (h; B) from h to each body where it occurs positively; a negative edge (h; B) from h to each body where it occurs negatively. – The Rule-Head Graph has rules and heads as vertices, and: an edge (r; h) from each rule r ∈ P and its head h; a positive edge (h; r) from h to each rule where it occurs positively in the body; a negative edge (h; r) from h to each rule where it occurs negatively in the body. – The Body-Rule Graph has bodies and rules as vertices, and: an edge (B; r) from each body B ∈ Body(P ) to each rule r ∈ P whose body is B; a positive edge (r; B) from r to each body where the head h of r occurs positively; a negative edge (r; B) from r to each body where the head h of r occurs negatively.
Some combinations/variations of the above three representations are also defined in the above-mentioned papers.
These representations have been used as a basis for implementing the noMoRe
answer set solver [
However, none of them is isomorphic. In particular, they are acceptable and adequate but not unambiguous. In fact, atoms that are not defined (i.e., that do not occur in the head of any rule) are never considered in the definitions. Take for instance the programs {a ← b:} and {a ← b; c:}. Indicate, e.g., the rule with r1 and its body with B1. These two programs have structurally identical graphs. We cannot distinguish between the two cases unless we explicitly associate the program to the graph (e.g., by copying rules and bodies into the vertices as labels). 7
Graph representations of logic programs can be useful from a software engineering perspective. We have defined which properties a graph representation should posses in order to be a good program representation tool, and we have compared different representations w.r.t. these properties. Topics of further research are that of demonstrating effective usefulness of graph representations for program analysis and construction.
We consider the language DAT ALOG¬ for deductive databases, which is more
restricted than traditional logic programming (the reader may refer to [
A general logic program (or simply “logic program”) is composed of rules may contain negated atoms of the form ¬a. A rule is defined as usual, and can be seen as composed of a conclusion head( ), and a set of conditions body( ). The latter can be divided into positive conditions pos( ) each one of the form A, and negative conditions neg( ), each one of the form not A. The literal A is either an atom a, or a negated atom ¬a. A negative logic programs is composed of rules without positive conditions.
The answer sets semantics [
A subset M of the Herbrand base BP of a DAT ALOG¬ program P is an answer set of P , if M coincides with the least model of the reduct P M of P with respect to M . This reduct is obtained by deleting from P all rules containing a condition not a, for some a in M , and by deleting all negative conditions form the other rules. Answer sets are minimal supported models, and form an anti-chain.
Unlike with other semantics, a logic program may have several answer sets, or may have no answer set, because conclusions are included in an answer set only if they can be justified. The following program has no answer set: {a ← not b: b ← not c: c ← not a:} The reason is that in every minimal model of this program there is a true atom that depends (in the program) on the negation of another true atom. Whenever a program has no answer sets, we will say that the program is inconsistent. Correspondingly, checking for consistency means checking for the existence of answer sets.
Every logic program can be reduced to its kernel normal form [
In the following sections, by “logic program” we will implicitly refer to a general logic program. When explicitly indicated, we will refer to a negative program or to a kernel program.
B
The graph representations that we introduce in the following are all based on directed
graphs. Then, in this paper the term “graph” refers implicitly to directed graphs. Below
we introduce some basic definitions about graphs. For a comprehensive presentation
and discussion on graphs and graph theory the reader may refer for instance to [
A directed graph or graph G is a pair ⟨V; E⟩. V is a set, whose elements are called vertices or nodes. The elements of E, where E ⊆ V × V , are called the edges of the graph. For each edge e ∈ E, where e = (vi; vj ), vi; vj ∈ V , we say that e goes from vi to vj , and, referring to vj , that e is an edge coming from vi. Let G be a graph, and V ′ ⊆ V . Let V \ V ′ be the set of vertices that are are in V but not in V ′.
A labeled directed graph or labeled graph G is a triple ⟨V; E; L⟩ where V is as before, L is a set of labels, and the elements of E, where E ⊆ V × V × L, are now of the form e = (vi; vj ; l), vi; vj ∈ V , l ∈ L. All definitions given here for directed graphs can be easily rephrased for labeled directed graphs, and then in the rest of the paper we often give this reformulation for granted.
Given a directed graph and vertices a; b ∈ V (where it can be a = b) a path P from a to b is a subset E′ of E where either E′ = (a; b) or there exists edge (a; c) ∈ E′ such that E′ \ (a; c) is a path from c to b. We say that P is composed of the edges (x; y) in E′ and involves vertices x; y. By abuse of notation we also consider these vertices as belonging to the path, and we say x; y ∈ P . A cycle C is a set of edges which constitutes a path from v to v, for some v ∈ V .
A simple path from a to b is a path P such that there not exist P ′ ⊂ P such that P ′ is a path from a to b. Vertex a is called the source of the path, while vertex b is called the sink. A simple cycle C is a set of edges which constitutes a simple path from v to v, for some v ∈ V . In the following, by “a cycle” we will implicitly mean a simple cycle. A cycle is even (resp. odd) if it is composed of an even (resp. odd) number of distinct edges.
A kernel in a directed graph is a subset V ′ of V such that (i) no two vertices in V ′ are joined by an edge in E (we say that V ′ is independent), and (ii) for every vertex v ∈ V − V ′ there is some vertex v′ ∈ V ′ where (v′; v) belongs to E (we say that V ′ is dominating).
Let E=V ′ be E ∩ (V ′ × V ′). The subgraph of G induced by V ′ is the graph G′ = ⟨V ′; E=V ′⟩. If V ′ is a kernel, it is easy to see that (by condition (i) above) the induced subgraph has an empty set of edges.
For a negative logic program P (and in particular for a kernel program P ), its dependency graph DG(P ) is a finite directed graph whose vertices are the atoms occurring in P . There is an edge (w; v) if and only if there is a rule in P with v in its head and not w occurring in its body. In the DG, we say that atom a depends on atom b if there is a path from b to a.
For a general logic program P , its dependency graph DG(P ) is a finite directed labeled graph whose vertices are the atoms occurring in P and whose set of labels is {+; −}. There is an edge (w; v; +) if and only if there is a rule in P with v in its head and w occurring in its body (positive edge). There is an edge (w; v; −) if and only if there is a rule in P with v in its head and not w occurring in its body (negative edge).
In the DG, we say that atom a depends on atom b if there is a path from b to a. Atom a depends evenly (resp. oddly) on b if there exists a path between a and b composed of an even (resp. odd) number of arcs. A program is stratified if no atom depends on itself. As a special case one can have positive dependencies, that can be either even or odd, by considering (and thus counting) only the positive edges of the path. Similarly, one can consider negative dependencies, that can be either even or odd, by considering (and thus counting) only the negative edges of the path. A program is stratified if in its DG no atom depends on itself: i.e., for no atom a there is a cycle involving a.
A loop, or cycle, in a program corresponds to a cycle on its Dependency Graph DG(P ). A cycle composed of positive edges only is called a positive cycle. A cycle composed of negative edges only is called a negative cycle. Positive and negative cycles are either even or odd depending on the number of edges. A cycle which is not positive is said to be either even or odd according to the number of negative edges only, because consistency of the program is mainly affected by negative dependencies. A program is call–consistent if on its DG no atom has an odd negative dependency on itself: i.e., there is no cycle involving a and including an odd number of negative edges. Stratified and call–consistent programs are guaranteed to be consistent under the answer set semantics (answer sets always exist).