Towards the Use of Hypergraphs in Multi-adjoint Logic Programming

Towards the Use of Hypergraphs in Multi-adjoint Logic Programming Juan Carlos Díaz-Moreno, Jesús Medina and José R. Portillo Abstract The representation of a logic program by a graph is a useful procedure in order to obtain interesting properties of the program and in the computation of the least model, when it exists. In this paper, we consider hypergraphs for representing multi-adjoint logic programs and, based on this representation, the hypotheses of an interesting termination result have been weakened. 1 Introduction One of the most important problems in logic programming with non-decreasing operators is the computation of the least model of a given program. In order to obtain such a model the fix-point semantics is usually considered. This semantics is based on the iteration of the immediate consequence operator from the least interpretation. Since this iteration can be infinite, one important goal is to get termination properties of this iteration. In [3,4], different termination theorems were introduced in the multi-adjoint logic programming. This logic programming framework was introduced in [10] as a generalization of different non-classical logic programming frameworks, such as the residuated logic programming [5] and the fuzzy logic programming framework presented in [11]. This paper considers directed hypergraphs [1,8] in order to represent a multiadjoint logic program and, based on this representation, introduce a termination result, which generalizes one of the most important termination theorems given in [4]. J. C. Díaz-Moreno · J. Medina Department of Mathematics, University of Cádiz, Cádiz, Spain e-mail: [email protected] J. Medina e-mail: [email protected] J. R. Portillo (B) Department of Applied Mathematics I, University of Sevilla, Sevilla, Spain e-mail: [email protected] 2 Basic Definitions on Hypergraphs This section recalls the notions we will need throughout the paper related to hypergraphs. For basic notions of graph theory see [2]. Agraph is a pair of sets (V,E).Vis the set of vertices or nodes.Eis a set of 2-element subsets of V, named edges. The edges may be directed or undirected (the pairs are ordered or not). Directed edges are called arcs.Acycle in a graph is a path of edges and vertices wherein a vertex is reachable from itself. I.e., a ordered set of vertices {u1,...,ui,...up}such that uiui+1is an edge of the graph and u1=up. Thefirstnotionforhypergraphs is the definition, which is a generalization of a graph in which an edge is a non-empty subset of vertices. Specifically, a hypergraph His a pair H=(V,E)where Vis a set of elements called nodes or vertices, and Eis a set of non-empty subsets of Vcalled hyperedges or edges, see [2]formore details. Therefore, Eis a subset of P(V)\{∅}, where P(V)is the power set of V. Note that, when the cardinal of all hyperedges is 2, the hypergraph is a standard graph. The generalization of a directed graph is called directed hypergraph and contains directed hyperedges. A directed hyperedge or hyperarc is an ordered pair, e=(X,Y), of (possibly empty) disjoint subsets of vertices; Xis called the tail of eand Yis its head. From now on, the tail and the head of an hyperarc ewill be denoted by T(e) and H(e), respectively. Hence, a directed hypergraph is a hypergraph with directed hyperedges [1,8]. Abackward hyperarc,orsimplyB-arc, is a hyperarc e=(T(e), H(e)), where the head exactly has one vertex. When all the hyperarcs of a hypergraph are B-arcs, then the hypergraph is called B-graph (or B-hypergraph)[8]. For example, the hypergraph H=(V,E)introduced on the left of Fig.1, where V={a,b,c,d} and E={({a},{b}), ({b,c},{a}), ({c,d},{a})}is a B-graph. This paper will only consider this kind of hypergraphs. B-graphs (and the dually defined F-graphs) are a useful tool in different applications [1,8,9]. As a consequence, they have been introduced many times in the literature with various names. For example, the labelled graphs, used in [6,7]to represent Horn formulae, are B-graphs. b c d a b c d a Fig. 1 Left: Example of B-graph H=(V,E). Right: Directed graph subjacent to H In contrast with ordinary graphs for which there is a single natural notion of cycles and acyclic graphs, there are multiple natural non-equivalent definitions of acyclicity for hypergraphs which collapse to ordinary graph acyclicity for the special case of ordinary graphs. In this paper, we only need to consider the cycles on the subjacent directed graph of a B-graph. Given any directed hypergraph H=(V,E), the subjacent directed graph G(H)=(V(G), E(G)) has the same nodes that H, i.e. V(G)=Vand an arc exists in E(G)from the node uto the node vif and only if it exists a hyperedge e∈Esuch that u∈T(e)and v∈H(e). For example, Fig.1shows on the right the subjacent graph to the hypergraph on the left. The vertices aand bform a cycle in that graph, but the hypergraph has not hypercycles under the common definitions [2]. 3 Multi-adjoint Logic Programming This section recalls the algebraic structure considered in this framework, the notion of multi-adjoint logic program, and one of the most interesting termination theorems introduced in [4]. The basic operators considered in this framework are adjoint pairs. Definition 1 Given a partially ordered set (P,≤), the pair (&,←)is an adjoint pair with respect to (P,≤)if the mappings &,←: P×P→Psatisfy that: 1. &is order-preserving in both arguments. 2. ←is order-preserving in the first argument (the consequent) and order-reversing in the second argument (the antecedent). 3. The equivalence x≤y←zif and only if x&z≤yholds, for all x,y,z∈P. The algebraic structure considered in this logic programming framework is called multi-adjoint lattice. Definition 2 Amulti-adjoint lattice is a tuple (L,,←1,&1,...,←n,&n)verifying the following properties: 1. (L,)is bounded lattice, i.e. it has bottom (⊥)and top ()elements; 2. (&i,←i)is an adjoint pair in (L,), for all i∈{1,...,n}; 3. &iϑ=ϑ&i=ϑ, for all ϑ∈Land for all i∈{1,...,n}. Given a multi-adjoint lattice, a set of propositional symbols Π, a given language denoted as Fand different monotonic operators defined on L, the notion of program (set of rules) is introduced in this framework. Definition 3 Given a multi-adjoint lattice (L,,←1,&1,...,←n,&n).Amultiadjoint logic program Pis a set of rules of the form (A←iB), ϑsuch that: 1. The rule (A←iB)is a formula of F; 2. The confidence factor ϑis an element (a truth-value) of L; 3. The head of the rule Ais a propositional symbol of Π. 4. The body formula Bis a formula of Fbuilt from propositional symbols B1,...,Bn (n≥0) by the use of conjunctors &1,...,&nand ∧1,...,∧k, disjunctors ∨1,...,∨l, aggregators @1,...,@mand elements of L. 5. Facts are rules with body . This paper will be focused on one of the most important theorems introduced in [4]. Before recalling this result we need different definitions. Definition 4 Let Pbe a multi-adjoint program, and A∈Π.ThesetRI P(A)of relevant values for Awith respect to an interpretation Iis the set of maximal values of the set {ϑ&iˆ I(B)|A←iB,ϑ∈P}. The immediate consequences operator, given by van Emden and Kowalski, is defined in this framework as follows. Definition 5 Given a multi-adjoint logic program P.Theimmediate consequences operator TPmaps interpretations to interpretations, and for an interpretation Iand an arbitrary propositional symbol Ais defined by TP(I)(A)=sup{ϑ&iˆ I(B)|A←iB,ϑ∈P} The main feature of TPis that its least fix-point coincides with the least model of the program P[10]. Since the least fix-point is computed iterating the TPoperator from the least interpretation, Δ, it is important to know when this iteration finishes in a finite number of steps. The termination theorem in [4] was introduced for sorted and local multi-adjoint logic programs. In order to simplify the notation, we have adapted it for (uni-sorted) multi-adjoint logic programs. Theorem 1 Given a multi-adjoint logic program Pwith finite dependences and where the operators @:Lm→L in the body of the rules satisfy the boundary condition with the element, that is, @(,...,   k ,x,,...,   m−k−1 )x for all x ∈L. If for every iteration n and propositional symbol A the set of relevant values for A with respect to T n P()is a singleton, then TPterminates for every query. This result will be weakened in the following section. 4 Representing Programs by Hypergraphs This section presents a simple example which does not satisfy the hypotheses of Theorem 1, but the least model of the program is obtained after finitely many iterations. Then, in order to extend this result to a bigger number of programs, a straightforward mechanism for representing a logic program by a B-graph is introduced. Finally, based on this representation, the hypotheses of Theorem 1will be weakened. Example 1 Consider the following program P: a←Pb&Gc,0.8b←Pa,0.7 a←P@(d,c), 1.0c←P1.0,1.0 a←P1.0,0.5 where the aggregator @:[0,1]×[0,1]→[0,1]is the weighted sum defined as @(x,y)=(x+3y)/4, for all x,y∈[0,1]. Although the minimum operator&Gsatisfies the boundary condition with the 1 element (hypothesis in Theorem 1), the aggregator @ does not verify it and so, we cannot apply this theorem in order to know whether the computation of the least model terminates in a finite number of iterations. However, in this case, only 3 iterations are needed, as we show below: abcd TP0=0.00.00.00.0 TP1=0.75 0.01.00.0 TP2=0.75 0.525 1.00.0 TP3=0.75 0.525 1.00.0 This example shows that the hypotheses in Theorem 1should be weakened. For that, we will represent a program by a B-graph and we will relate the termination of the iterations to the existence of cycles in the subjacent directed graph and whether aggregator operators, which do not satisfy the hypotheses of the theorem, are involved in these cycles. Note that, it has been possible to compute the least model in a finite number of iterations because the aggregator operator @ is not in a cycle of the subjacent digraph of the associated B-graph. The associated B-graph HPassociated with a program Pis constructed as follows: the vertex set of the hypergraph is the propositional symbol set Πof the program. Hence, for the program Pin Example 1,wehaveV(HP)={a,b,c,d}. One hyperarc will be obtained from each rule as follows: Given a rule, the propositional symbols of the antecedent of the rule will be the tail T(e)of the associated hyperarc and the propositional symbol of the head of the rule will be the only element of the head H(e)of the associated hyperarc. This hyperarc is labeled with the aggregator in the body of the rule. When no aggregator operator appears in the body of the rule, we will b c d a & G @ ld b c d a &G @ @ & G ld Fig. 2 Left: (Labelled) B-graph associated with the program given in Example 1. Right: (Labelled) Subjacent directed graph from the B-graph on the left consider the identity mapping. For example, from the rule a←Pb&Gc,0.8for the program Pin Example 1, we obtain the hyperarc ({b,c},{a})with the label &G. Due to the considered mechanism, the hypergraph resultant is always a (labelled) B-graph. Figure2(left) shows the associated B-graph of the program Pgiven in Example 1. Finally, a weak version of Theorem 1is introduced: Theorem 2 Given a multi-adjoint logic program Pwith finite dependences and the B-graph HPassociated with P. If the operators involved in the cycles of the subjacent directed graph of HPsatisfy the boundary condition with the element and, for every iteration n and propositional symbol A, the set of relevant values for A with respect to T n P()is a singleton, then TPterminates for every query. Note that this result only needs that the aggregators operators involved in the cycles of the subjacent directed graph of the B-graph associated with the program satisfy the boundary condition. Therefore, this result is notably more general than Theorem 1and can be applied, for example, to the program given in Example 1. 5 Conclusions and Future Work This paper has presented a procedure in order to represent a multi-adjoint logic program as a hypergraph. As a first consequence, we have generalized one of the most important termination results introduced in [4]. This representation will provide more interesting properties in the future. We will study other efficient termination results and we will analyze analogies between different notions in logic programming and in graph theory in order to create synergies between both theories. The obtained results will also be compared with the existent ones in the literature. References 1. Ausiello, G., Laura, L.: Directed hypergraphs: introduction and fundamental algorithms—a survey. Theor. Comput. Sci. 658, 293–306 (2017) 2. Berge, C.: Graphs and Hypergraphs. Elsevier Science Ltd. (1985) 3. Damásio, C., Medina, J., Ojeda-Aciego, M.: Sorted multi-adjoint logic programs: termination results and applications. In: Lecture Notes in Artificial Intelligence, vol. 3229, pp. 252–265 (2004) 4. Damásio, C., Medina, J., Ojeda-Aciego, M.: Termination of logic programs with imperfect information: applications and query procedure. J. Appl. Log. 5, 435–458 (2007) 5. Damásio, C.V., Pereira, L.M.: Monotonic and residuated logic programs. In: Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2001. Lecture Notes in Artificial Intelligence, vol. 2143, pp. 748–759 (2001) 6. Dowling, W.F., Gallier, J.H.: Linear-time algorithms for testing the satisfiability of propositional Horn formulae. J. Log. Program. 1(3), 267–284 (1984) 7. Gallo, G., Urbani, G.: Algorithms for testing the satisfiability of propositional formulae. J. Log. Program. 7(1), 45–61 (1989) 8. Gallo, G., Longo, G., Pallottino, S., Nguyen, S.: Directed hypergraphs and applications. Discrete Appl. Math. 42(2–3), 177–201 (1993) 9. Jeroslow, R.G., Martin, R.K., Rardin, R.L., Wang, J.: Gainfree Leontief substitution flow problems. Math. Program. 57, 375–414 (1992) 10. Medina, J., Ojeda-Aciego, M., Vojtáš, P.: Multi-adjoint logic programming with continuous semantics. In: Lecture Notes in Artificial Intelligence, vol. 2173, pp. 351–364 (2001) 11. Vojtáš, P.: Fuzzy logic programming. Fuzzy Sets Syst. 124(3), 361–370 (2001)