Fuzzy logic programs as hypergraphs. Termination results

JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.1 (1-21) Available online at www.sciencedirect.com ScienceDirect Fuzzy Sets and Systems ••• (••••)•••–••• www.elsevier.com/locate/fss Fuzzy logic programs as hypergraphs. Termination results ✩ Juan Carlos Díaz-Moreno a, Jesús Medina a,∗, José R. Portillo b aDepartment of Mathematics, University of Cádiz, Spain bDepartamento de Matemática Aplicada I and Instituto Universitario de Investigación de Matemáticas de la Universidad de Sevilla (IMUS), Universidad de Sevilla, Spain Received 8 February 2021; received in revised form 19 January 2022; accepted 1 February 2022 Abstract Graph theory has been a useful tool for logic programming in many aspects. In this paper, we propose an equivalent representation of multi-adjoint logic programs using hypergraphs, which are a generalization of classical graphs that allows the use of hypergraph theory in logic programming. Specifically, this representation has been considered in this paper to increase the level and flexibility of different termination results of the computation of the least model of fuzzy logic programs via the immediate consequence operator. Consequently, the least model of more general and versatile fuzzy logic programs can be obtained after finitely many iterations, although infinite programs or programs with loops and general aggregators will be considered. ©2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). Keywords: Logic programming; Fuzzy sets; Termination; Hypergraphs 1. Introduction Logic programming [45]is an important framework to obtain information from a dataset, which has been modeled by a set of logic rules that are called either ‘logic program’ or simply ‘program.’ Therefore, logic programming is a core part of decision and recommendation systems, among others. Many researchers have studied logic programming from a theoretical point of view and it has been applied to many frameworks [8,9,12,13,15,35,40,43,55]. Several fuzzy extensions have been introduced to handle imprecise, incomplete or imperfect data [21,36,44,23,48–50]. Multi-adjoint logic programming arose as a general logic-programming framework, which embeds residuated and monotonic logic programming, fuzzy logic programming, probabilistic logic programming, and so on. The main idea behind this general framework is to consider the most general mathematical setting from which the most useful results can be proved. Consequently, the semantics is based on a complete ✩Partially supported by the 2014-2020 ERDF Operational Programme in collaboration with the State Research Agency (AEI) in project PID2019- 108991GB-I00, and with the Department of Economy, Knowledge, Business and University of the Regional Government of Andalusia in project FEDER-UCA18-108612, and by the European Cooperation in Science & Technology (COST) Action CA17124. *Corresponding author. E-mail address: [email protected] (J. Medina). https://doi.org/10.1016/j.fss.2022.02.001 0165-0114/©2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.2 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• lattice in which (for example) the operators can be neither commutative nor associative, and different implications can be taken into account in the same logic program. These general structures allow the consideration of a more flexible and suitable set of rules to better simulate the behavior of a given knowledge system. An important issue in multi-adjoint logic programming is to compute the consequences (least model) that are associated with the dataset modeled by the program (computed set of rules); that is, the values from which we can offer predictions and recommendations to the user. These values can be obtained in this and in many other frameworks by the immediate consequence operator TPfor a program P[27,59]. Specifically, the least model is obtained by iterating the TPfrom the least interpretation (which associates the bottom of the lattice with every atom) until a fixed point is obtained. We must take into account that in many cases it is difficult to know whether the computation of the least fixed point of TPfinishes for every query (e.g., when the considered program has infinite rules and/or has loops). Therefore, an important goal in these (fuzzy) logic programs is to know a priori when the computation of the least model will terminate in a finite number of iterations; that is, if TPterminates, which has been studied in many papers [18,22,25,44,23,52]. In [20], the authors introduced several interesting termination theorems that are based on the notion of dependency graph, together with useful applications to probabilistic programs, such as ordinary probabilistic logic programs, probabilistic deductive databases, and hybrid probabilistic logic programs. This paper considers the theory of hypergraphs [10]to provide an efficient representation of a given logic program and to increase the level and flexibility of the termination theorems given in [20]. In particular, we use directed hypergraphs [6,30], which appear in a lot of different contexts, such as propositional logic [5,24,25,31,32,53], artificial intelligence [51], technological processing of product assembly [47], relational databases [7,62], probabilistic parsing [42], chemical reaction mechanisms [63], operations research [30], transportation planning [54], Petri nets [1], and so on. Alongside this work, we will focus on a special kind of directed hypergraphs, namely B-graphs, which have been used as a tool to analyze deductive databases (see [3,6,30,61]) and to solve Horn formulae [11,26,56,57]. B-graphs are also used to study Leontiev substitution matrices and flow problems [34], and to plan urban transportation [54]. Several relationships among graphs, hypergraphs and logic programs have been studied. Consequently, it has been possible to translate the information given in a program to a hypergraph, and vice versa. In fact, the proposed computation of a labeled B-graph from a program keeps all of the information provided by the program, while the dependency graph, even when labeled, loses some information. Obviously, this loss can be avoided by relabeling the edges of the dependency graph. However, in that case the obtained structure is equivalent to a hypergraph but represented in a way that is more complex and computationally less manageable than this one. Hence, hypergraphs provide a simpler and more tractable representation of logic programs (i.e., there is only one labeled hyperarc for each rule instead of multiple edges with the same label). This representation facilitates visualizing, and gives additional insight into, the structure of multi-adjoint logic programs. This allows us to demonstrate new results and open up promising new lines of investigation. The first termination theorem is proved based on the obtained hypergraph and other intermediate results. A variant of this hypergraph has been analyzed to prove the second termination theorem, which significantly increases the number of operators that can be used in the program. Both of these theorems generalize the main results presented in [20] and provide a broader range of applications, from which we can know in advance if the computation of the least model terminates in a finite number of iterations. Note that it is not possible to directly apply the result in [20] only considering dependency graphs, they must be adapted and extra results are required. However, the underlying mathematical proofs are similar to those proved in this paper. Hence, hypergraphs have been considered not only because they improve the representation of the program but they also provide a better understanding of the hypotheses and (aesthetically) simplification of different parts of the proofs. The rest of this paper is structured as follows. Section 2includes the preliminary notions to be used throughout the paper. Section 3presents the results relating to graphs and hypergraphs, and the representation of programs by hypergraphs, which have been applied to the termination results given in Section 4. In the final section, this paper draws the conclusions and looks to the prospects for future work. 2. Preliminaries The main notions in hypergraph theory and multi-adjoint logic programming considered in this paper are recalled next. 2 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.3 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• Fig. 1. Example of B-graph H=(V , E). 2.1. Basic definitions of hypergraphs This section recalls the notions related to hypergraphs that we will need throughout this paper. For the basic notions of (hyper)graph theory, see [10]. A graph is a pair of sets (V, E), where Vis the set of vertices or nodes and Eis a subset of unordered pairs of vertices, which are called edges. A hypergraph is a generalization of the notion of a graph in which an edge can join any number of vertices. The generalization is given through the notion of hyperedge. Specifically, a hypergraph is defined as a pair of sets (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 [10]for more details). Note that a graph is a kind of hypergraph verifying that the cardinal of all hyperedges is two. A directed graph or digraph is a graph whose edges are ordered pairs of vertices. The corresponding generalization of a directed graph is called a directed hypergraph [6,30]. Formally, a directed hypergraph is a pair of sets (V, E), where the elements of Eare called directed hyperedges or hyperarcs and each of them is an ordered pair, e=(X, Y), of disjoint subsets of vertices. We denote Xas the tail of eand Yas its head. Hereinafter, the tail and the head of a hyperarc ewill be denoted by T(e)and H(e), respectively. Hence, a directed hypergraph is a hypergraph with directed hyperedges. In the following, when no confusion arises, directed hypergraphs will simply be called hypergraphs. Given a graph G =(V , E), a vertex labeling is a function of Vto a set of labels. A vertex-labeled graph is a graph with one or more associated vertex labeling functions. Likewise, an edge labeling is a function from Eto a set of labels and we say that a graph with an edge labeling is an edge-labeled graph. The definition of labeled graphs is extended to digraphs and (directed) hypergraphs, in a natural way. A backward hyperarc, or simply B-arc, is a hyperarc e, where the head H(e)has exactly one vertex; that is, it is a singleton. In a similar way, forward hyperarc, or simply F-arc, is a hyperarc fwhere the tail T(e)exactly has one vertex. When all of the hyperarcs of a hypergraph are B-arcs (resp. F-arcs), then the hypergraph is called B-graph (resp. F-graph)[30]. Note that a digraph is simultaneously a particular case of a B-graph and an F-graph. For example, the hypergraph H=(V , E) introduced in Fig. 1, where V={a, c, f, h, n, u}and E={({c}, {n}), ({f}, {h}), ({f, h}, {n}), ({f, h}, {u}), ({f, u}, {a}), ({n, u}, {c}), ({u}, {f})}is a B-graph with six vertices and seven B-arcs. This paper will only consider this kind of directed hypergraph. Because hyperarcs provide a natural representation of Horn formulae and databases, B-graphs and F-graphs are useful for many applications [5,6,30–32,34,61]. Indeed, they have been presented many times with different names in the literature. For example, the B-graphs are called “labeled graphs” (not to be confused with the two labeled graphs that were defined previously) in [26,32,57]to represent the Horn formulae. Torres and Araoz [61] studied hypergraphs and B-graphs, called “rule hypergraphs”, to represent deduction properties in databases as paths in hypergraphs. Ausellio and Italiano [5]also used this kind of directed hypergraph, although they called them “FD-graphs”, for construct polynomial algorithms to solve satisfiability problems. In this work, we will use labeled B-arcs as a natural representation of rules in a multi-adjoint logic program. The notion of a subgraph is extended to directed hypergraphs in [60]. Definition 1. Given a directed hypergraph H=(V, E), we say that H=(V , E)is a subhypergraph of Hif Vis a subset of Vand Eis a subset of E∩(2V×2V). The definition of hypergraph induced by the set of vertices Vis adapted from [58]to directed hypergraphs and it is the subhypergraph H=(V , E), where E=E∩(2V×2V). The following definition has been adapted from [30,60]. 3 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.4 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• Fig. 2. Directed graph subjacent to the directed hypergraph in Fig. 1. Definition 2. Given a directed hypergraph H=(V, E), two vertices s, t∈V, and a natural number q, a path in H from sto tof length q, denoted as Pst, is a sequence of nodes and hyperarcs: Pst =v1, E1, v2, E2, ..., vq, Eq, vq+1 where: v1=s, vq+1=t, s∈T(E 1), t∈H(Eq), and vi∈H(Ei−1) ∩T(E i), for all i∈{2, ..., q}. The trivial sequence v, with v∈V, will be a path of length 0. Nodes sand tare the origin (source) and the destination (sink) of Pst, respectively, and we say that tis connected to sor that tis weakly reachable from s[29]. ‘Weakly’ is used because some applications of directed hypergraphs (e.g., assembly or databases) need a different and strong notion of reachability [7]. If t∈T(E 1), then Pst is said to be a cycle [30]. In particular, this is true when t=s. Note that if there is a cycle from sto t, then there is also a cycle from tto t. There are different definitions for paths in directed hyperarcs in the literature [2–4,6,10,30,60]. We have considered the definition introduced in [30] and [60], which is better suited to the aims of this paper and is less restricted than the definitions given in other papers. Given that we are considering B-graphs, a path Pst =s, E1, v2, E2, ..., Eq, tis univocally determined by its B-arcs and its origin because viis the only vertex in the head of Ei−1. In this case, we can denote the path as Pst =s, E1, E2, ..., Eq, t. For example, in the B-graph shown in Fig. 1, f, ({f}, {h}), ({f, h}, {u}), ({u}, {f}), fand c, ({c}, {n}), ({n, u}, {c}), care cycles. Every directed hypergraph is associated with a digraph. Definition 3. Given a directed hypergraph H=(V, E), the primal digraph (or subjacent digraph) D(H) =(V, A) of the hypergraph Hhas the same nodes that the hypergraph and an arc exists in Afrom 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. 2shows the subjacent digraph to the B-graph in Fig. 1. The cycles f, ({f}, {h}), ({f, h}, {u}), ({u}, {f}), fand c, ({c}, {n}), ({n, u}, {c}), cin the B-graph correspond to the cycles f, h, u, fand c, n, cin the primal graph. Note that the correspondence is not injective because two directed hypergraphs can be associated with the same digraph. 2.2. Multi-adjoint logic programming In this section, we recall the notion of a multi-adjoint logic program and the most interesting termination theorems that were introduced in [20]. We will first present the so-called adjoint pairs. These are the basic operators considered in this framework. They generalize left-continuous t-norms and their residuated implications. Definition 4. 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≤z←yif and only if x&y≤zholds, for all x, y, z∈P. 4 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.5 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• Note that the pairs composed of the product, Gödel and Lukasiewicz t-norms and its corresponding residuated implication, which will be denoted as (&P, ←P), (&G, ←G), (&Ł, ←Ł), and are defined, for each x, y, z∈[0, 1], as x&Py=x·yz←Py=1ify≤z z yif y>z x&Gy=min{x,y}z←Gy=1ify≤z zif y>z x&Ły=max{0,x+y−1}z←Ły=min{1,1−y+z} are adjoint pairs. Clearly, these operators have infinite range (i.e., the image set is infinite). The following examples show particular cases of adjoint pairs, which correspond to operators with finite range. Example 5. Let [0, 1]mbe a regular partition of [0, 1]into mpieces; for example, [0, 1]4={0, 0.25, 0.5, 0, 75, 1} divides the unit interval into four pieces. A discretization of a t-norm &:[0, 1] ×[0, 1] →[0, 1]is the operator &∗:[0, 1]m×[0, 1]n→[0, 1]k, where n, m, k∈N, defined for each x∈[0, 1]mand y∈[0, 1]nas: x&∗y=k·(x &y) k where  _is the ceiling function. The discretization of the corresponding residuated implication ←∗:[0, 1]k×[0, 1]n→[0, 1]mis defined as: z←∗y=m·(z ←y) m where  _is the floor function and ←is the residuated implication of the t-norm &. We have that (&∗, ←∗)is an adjoint pair in the unit interval [16,48], and &∗, ←∗have finite range.  The considered algebraic structure contains this general kind of operators and is called a multi-adjoint lattice. Definition 6. A multi-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 i∈{1, ..., n}. Multi-adjoint lattices were fundamental in [20, Definition 26] to define the general algebraic structure taken into account in the aforementioned paper, which is called local sorted multi-adjoint -algebra. To simplify the notation, in this paper only one sort will be considered. Definition 7. A local multi-adjoint -algebra Lis a multi-adjoint lattice (L, ,←1,&1,...,←n,&n) on which other operator is defined, such as conjunctors ∧1, ..., ∧k, disjunctors ∨1, ..., ∨land general aggregators @1, ..., @h. The set of those monotonic operators (aggregator operators, in particular) in the -algebra will be denoted as A; that is, A={&1,...,&n,∧1,...,∧k,∨1,...,∨l,@1,...,@h} and each operator @:Lm→Lin Asatisfies the boundary condition with the top element: @(,...,   s ,x,,...,   m−s−1 )x(1) for all x∈L. 5 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.6 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• From now on, a local multi-adjoint -algebra L, a set of propositional symbols and a language denoted as F will be fixed. From these notions, we can introduced the definition of multi-adjoint logic program (set of rules). Definition 8. A multi-adjoint logic program is a set of rules of the form A←iB,ϑsuch that: 1. The rule A ←iBis 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, ..., &rand ∧1, ..., ∧k, disjunctors ∨1, ..., ∨l, aggregators @1, ..., @mand elements of L. 5. Facts are rules with body . For a body formula B, as in point 4 of this definition, we can express it by @[B1, ..., Bn], where B1, ..., Bnare all propositional symbols in Band @the composition of the operators in B. For example, if B=(B1&B2) ∧B3, then it can be written as @[B1, B2, B3]; that is, @[B1, B2, B3] =(B1&B2) ∧B3=B. The following example introduces a particular multi-adjoint logic program. Example 9. We will consider the local multi-adjoint -algebra Fcomposed of the unit interval as a complete lattice, the adjoint pairs corresponding to the product, Gödel and Lukasiewicz t-norms, (&P, ←P), (&G, ←G), (&Ł, ←Ł), and the weighted sums @(3,1)and @(1,2)defined as @(3,1)(x, y) =3x+y 4and @(1,2)(x, y) =x+2y 3, for every (x, y) ∈[0, 1]2. On this -algebra F, the following program Pis defined, which simulates the behavior related to flu symptoms: c←Pn& Pu,0.8 n←Pc,0.8 n←P@(1,2)(h,f), 0.6 h←Pf,0.7 u←Gh&Łf,0.7 f←Pu,0.9 a←P@(3,1)(u,f), 1.0 f←P1.0,0.8 n←P1.0,0.5 where c, n, h, f, uand a correspond to cough, nasal ache, headache, fever, flu and muscle ache.  As we reported in the introduction, this paper is focused on the most important theorems introduced in [20]. Before recalling these results, we need several definitions. Definition 10. An interpretation is a mapping I: →L. The set of all interpretations is denoted as IL. Notice that each of these interpretations, by the unique homomorphic extension theorem, can be uniquely extended to the set of formulae F. The function obtained in this way from an interpretation Iis denoted by ˆ I. The ordering on the truth-values lattice Lcan be extended to the set of interpretations IL. Proposition 11. Let be the ordering defined on ILas, I1I2iff I1(p) I2(p), for I1, I2∈ILand p∈. The pair (IL, )is a bounded lattice. The least interpretation maps every propositional symbol to the least element ⊥ ∈L. The semantic of multi-adjoint logic programming is based on the following notions of satisfiability and model. Definition 12. Given an interpretation I∈IL, a weighted rule A←iB,ϑis satisfied by I, if ϑˆ I(A ←iB). An interpretation I∈ILis a model of a multi-adjoint logic program Pif all weighted rules in Pare satisfied by I. The immediate consequences operator, which was given by van Emden and Kowalski [27], is defined in this framework as follows. 6 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.7 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• Definition 13. Given a multi-adjoint logic program P, the immediate consequences operator TPmaps interpretations to interpretations, and for an interpretation Iand an arbitrary propositional symbol Ais defined as TP(I)(A) =sup{ϑ&iˆ I(B)|A←iB,ϑ∈P} The main feature of TPis that its least fixed-point, denoted by lfp(TP), coincides with the least model of the program P[49] and is obtained iterating the TPoperator from the least interpretation . As we also highlighted in the introduction, it is important to know when this iteration finishes in a finite number of steps. Definition 14. Let Pbe a multi-adjoint program, and A ∈. The set RI 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 culprit set for Awith respect to Iis the set of rules A ←iB, ϑof Psuch that ϑ&iˆ I(B)belongs to RI P(A). Rules in a culprit set are called culprits. The culprit collection for Tn P()(A) is defined as the set of culprits used in the recursive computation of Tn P()(A). The notion of termination used in [20], which we will also consider in this paper, is the definition of fixpointreachability of Kifer and Subrahmanian [41]. Definition 15. Let Pbe a multi-adjoint logic program with respect to a multi-adjoint -algebra Land a set of propositional symbols . We say that TPterminates for every query if for every propositional symbol A, there is a finite n such that Tn P()(A) is identical to lfp(TP)(A). An interesting termination theorem given in [20]was based on the notions of dependency graph and finite dependences. Definition 16. The dependency graph of a multi-adjoint logic program Pis a digraph where the vertices are the propositional symbols in , and there is an arc from a propositional symbol Ato a propositional symbol Bfor each rule with head Aand the body containing an occurrence of B. The dependency graph for a propositional symbol Ais the subgraph of the dependency graph containing all of the vertices connected to Aand corresponding edges. We say that a multi-adjoint logic program Phas finite dependences if the number of edges in the dependency graph for Ais finite for every propositional symbol A. Notice that a program can have finite dependences, even though the program has an infinite set of rules. A particular case was shown in Example 23 of [20], in which a countable infinite program with finite dependences was presented. Based on this definition, the following theorem was introduced in [20], which is one of the most important termination results given in the aforementioned paper. Theorem 17 ([20]). Let Pbe a multi-adjoint logic program with respect to a local multi-adjoint -algebra Land the set of propositional symbols , and having finite dependences. If for every iteration nand propositional symbol Athe set of relevant values for Awith respect to Tn P()is a singleton, then TPterminates for every query. Because we assume finite dependences, when the unit interval or any linear lattice is considered, for every iteration n, Tn P()(A) is a maximum for all propositional symbol Aand so, the previous theorem can be applied. Corollary 18 ([20]). Given a local multi-adjoint -algebra L, where the lattice is the unit interval [0, 1], and a multi-adjoint logic program P, having finite dependences, we have that TPterminates for every query. In addition, if the theorem cannot be applied to show termination results (e.g., in the case of Hybrid Probabilistic Logic Programs (HPLPs) appearing in [23], because operators employed to capture disjunctive probabilistic strategies do not satisfy the boundary conditions), then we have the following result, which is based on the notion of range dependency graph. 7 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.8 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• Definition 19. The range dependency graph of a multi-adjoint logic program Phas a vertex for each propositional symbol in . There is an arc from a propositional symbol Ato a propositional symbol Bif Ais the head of a rule with body containing an occurrence of B, which does not appear in a sub-term rooted by a function symbol having finite range. This definition reduces the dependency graph of a multi-adjoint logic program Premoving arcs associated with operators with finite range. Consequently, arcs involved in infinite loops can be removed, and so the loops can be broken. For example, &∗ Ł:[0, 1]10 ×[0, 1]10 →[0, 1]10 has a finite range because at most only 11 values can be obtained when this operator is used. Hence, if we have the rule A ←&∗ Ł(&P(A, B), B) ⊗&P(B, D), then the range dependency graph will not consider the subterm &∗ Ł(&P(A, B), B) and so the representation of the previous rule in the range dependency graph will be equivalent to the representation of the rule: A ←&P(B, D). We will say that a multi-adjoint program Phas range finite dependences, if for every propositional symbol A, the number of edges in the associated range dependency graph for Ais finite. On this notion, we have the following result. Theorem 20 ([20]). If Pis a multi-adjoint logic program with an acyclic range dependency graph having range finite dependences, then TPterminates for every query. Finally, the last result merges Theorems 17 and 20 to allow more flexible logic programs. Theorem 21 ([20]). Let Pbe a multi-adjoint logic program with respect to a local multi-adjoint -algebra with finite operators Land the set of propositional symbols , and having range finite dependences. If for every iteration nand propositional symbol Athe set of relevant values for Awith respect to Tn P()is a singleton, then TPterminates for every query. Although these results are useful and general, as we will show next, they do not allow the use of aggregator operators (e.g., weighted sums or disjunctive operators) in general, which is very suitable in many applications. Example 22. Given the program introduced in Example 9, the least model of the program through the immediate consequence operator TPwill be computed next. A simple implementation of the TPoperator can be done (e.g., in Python): c=n=h=f=u=a=0; c1=n1=h1=f1=u1=a1=0; count=0; while [c,n,h,u,f,a] < > [c1,n1,h1,u1,f1,a1] or count==0: c=c1;n=n1;h=h1;u=u1;f=f1;a=a1; c1=n∗u∗0.8; n1=max(c∗0.8,(h+2∗f)∗0.6/3,0.5); h1=f∗0.7; u1=min(max(0,(h+f−1)),0.7); f1=max(0.8,0.9∗u) a1=(3∗u+f)/4 print count,’’,f,’’,h,’’,u,’’,c,’’,n,’’,a count += 1; print count,’’,f,’’,h,’’,u,’’,c,’’,n,’’,a The results of the iterations of this program are depicted in Table 1. Therefore, the least model of the program is obtained after a finite number of iterations. However, the program does not satisfy the hypotheses of Theorems 17 and 21. Specifically, the weighted sums @(3,1)and @(1,2)do not verify the boundary condition with the top element. For example, we have @(3,1)(1, 0.5) =0.875 0.5 and @(1,2)(0.4, 1) = 0.8 0.4.  8 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.9 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• Table 1 Iteration of TPoperator from the least interpretation . fhuc na 0000 00 TP()0.8 0 0 0 0.5 0 T2 P()0.80.560 0 0.50.2 T3 P()0.80.560.360 0.50.2 T4 P()0.80.560.360.1440.50.47 T5 P()0.80.560.360.1440.50.47 Hence, Theorems 17 and 21 present interesting and useful termination results, but there are some cases in which the hypotheses are not satisfied, even though TPterminates for every query. Therefore, one important goal is to weaken the hypotheses or introduce new termination results that can be applied to a bigger range of logic programs. Therefore, hypergraphs instead of graphs will be taken into account to reformulate these theorems. The use of hypergraphs for representing logic programs is studied in the following section. 3. Representing programs by labeled directed hypergraphs The dependency graph of a program has been a useful tool for the termination results recalled above [20]. However, important information in the program is missing in the dependency graph. This is one of the most important reasons why hypergraphs are useful in this framework. Specifically, in this section we will use labeled directed hyperarcs instead of edges to capture more information about the relationships among the variables in the body of a rule, which are lost when only edges are considered. Consequently, we will show that the consideration of hyperarcs, and so hypergraphs, will provide a richer representation of the program than the dependency graph. 3.1. Edge-labeled B-graphs for representing multi-adjoint logic programs The notion of associated B-graph of a multi-adjoint logic program Pis first introduced. We then present the natural steps for computing such a hypergraph on an example. Definition 23. Given a multi-adjoint logic program P, the associated B-graph of Pis the edge-labeled B-graph HP=(, {(({B1,...,B n},{A}), @)|A←i@[B1,...,B n],ϑ∈P}) where (({B1, ..., Bn}, {A}), @)denotes the hyperarc ({B1, ..., Bn}, {A})with the label @. The B-graph HPassociated with a given program P, which is obtained from Definition 23, is constructed as follows: 1. The vertex set of the hypergraph is the propositional symbol set of the program. For instance, in Example 9, we have V(HP) ={a, c, f, h, n, u}. 2. Each program rule provides a hyperarc e, as follows: the propositional symbols of the body of the rule will be the tail T(e) of the hyperarc, and the propositional symbol of the head of the rule will be the only element of the head H(e). This hyperarc is labeled with the composition operator in the body of the rule. When no operator appears in the body of the rule, we will consider the identity mapping and we will avoid including the symbol in the representation of the hypergraph. For example, from the rule u←Ph& Lf, 0.7in Example 9, we obtain the hyperarc ({f, h}, {u})with label &L. Due to the considered mechanism, the obtained hypergraph is always an edge-labeled B-graph. Moreover, it is possible to obtain the original program from the hypergraph. Hence, both representations are equivalent. However, this fact does not hold for dependency graphs. Fig. 3shows the B-graph HPassociated with the program Pgiven in Example 9. Notice that HPis an edge-labeled hypergraph of the one associated with the example given in page 3. 9 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.16 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• Table 2 Computation of the lfp(TP)of program Pin Example 32. fh u c na 00 0 0 00 T1 P()0.8 0 0 0 0.5 0 T2 P()0.8 0.35 0 0 0.5 0.2 T3 P()0.8 0.35 0.15 0 0.5 0.2 T4 P()0.8 0.35 0.15 0.06 0.5 0.3125 T5 P()0.8 0.385 0.15 0.06 0.5 0.3125 T6 P()0.8 0.385 0.185 0.06 0.5 0.3125 T7 P()0.8 0.385 0.185 0.074 0.5 0.33875 T8 P()0.8 0.399 0.185 0.074 0.5 0.33875 T9 P()0.8 0.399 0.199 0.074 0.5 0.33875 T10 P()0.8 0.399 0.199 0.0796 0.5 0.34925 T11 P()0.8 0.399 0.199 0.0796 0.5 0.34925 Before introducing the aforementioned theorem, different definitions from [20] will be adapted into our framework and a technical lemma will be proved. From now on, we will consider a multi-adjoint logic program Pwith finite dependences, which are defined on a -algebra Lcontaining finite range operators, or simply finite operators. Hence, the bodies of the rules A ←iBj, ϑ in the program can be written as follows Bj=@j[gj 1(Dj 1),...,gj sj(Dj sj), Ci 1,...,Cj mj] where for each l∈{1, ..., sj}, the formula Dj lis a subterm of the body Bj, the argument of the outermost occurrence of a finite operator, which is denoted as gj l. The elements Cj lare the propositional symbols that are not influenced by finite operators, and @jis the aggregator operator given by the composition of all the operators in the body not in the scope of any finite operator. For each propositional symbol A, the set of all finite operators considered in PAwill be denoted as G(PA). For example, from the rule above, we have that gj 1, ..., gj sj∈G(PA). Because the finite operators can only increase a finite number of times, controlling this number in the iteration of TPwill be fundamental for proving one of the most important termination theorems presented in this paper. The following definition has been adapted from the one introduced in [20]. Definition 33. The counting sets for Pand Afor all n ∈N, denoted as SA n, are defined as follows: SA n={k<n|there is gj l∈G(PA)s.t. gj l( Tk−1 P()(Dj l)) < gj l( Tk P()(Dj l))} The hypergraph to be considered in the termination theorem will be a softer notion of the associated B-graph introduced in Definition 23, which accommodates Definition 19 to the hypergraph framework. Definition 34. Given a multi-adjoint logic program P, the associated range B-graph of Pis the labeled hypergraph Hr P, where the vertices are the propositional symbols used in Pand the labeled hyperarcs are the pairs (({Ci 1, ..., Cj mj}, {A}), @j)that are associated with each rule of the program A←i@j[gj 1(Dj 1),...,gj sj(Dj sj), Ci 1,...,Cj mj],ϑ Notice that the associated range B-graph of a program, Hr P, is a subhypergraph of HP. The associated range B-graph of the program in Example 32 is presented next. Example 35. The program in Example 32 only considers a finite range operator, which is used in the rule h←Pf&G∨∗ Ł(n,c), 0.7 16 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.17 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• Fig. 8. Associated range B-graph of program Pin Example 32. Hence, the associated range B-graph does not take into consideration the subterm ∨∗ Ł(n, c)because it is influenced by the finite range operator ∨∗ Łand the labeled hyperarc associated with this rule is (({f}, {h}), &G). The other hyperarcs are obtained as in page 9. Fig. 8depicts the associated range B-graph of P. The previous definitions will be taken into account to prove the following technical lemma. Notice that this result generalizes Lemma 39 in [20] and clarifies the proof in the last step because the application of the inductive hypothesis in the aforementioned result required some extra explanation. Lemma 36. Let Pbe a program on the -algebra L, where the s-hyperarcs of the associated range B-graph correspond to rules with an aggregator in the body satisfy Equation (1), and such that the set of relevant values for Awith respect to Tn P()is a singleton for every propositional symbol Aand iteration n. If Tn P()(A) <Tn+1 P()(A), then either |SA n| <|SA n+1|or the culprit collection for Tn+1 P()(A) is greater than that for Tn P()(A). Proof. The proof will be given by induction on n. For the base case (i.e., when n =0), we have that for every propositional symbol A, if ⊥ =(A) <T P()(A), then it is necessary that a new rule be considered. Now, we prove the inductive case. Hence, we suppose that the result is true for any propositional symbol and n =k, and we need to prove the result for k+1. If Tk P()(A) <Tk+1 P()(A), then by the singleton hypothesis, there is a rule in P ri=A←iBj,ϑ such that Tk+1 P()(A) =ϑ& Tk P()(Bj), where Bj=@j[gj 1(Dj 1), ..., gj sj(Dj sj), Cj 1, ..., Cj mj]). Concerning the iteration nbecause Tk P()(A) is the supremum of all contributions given by the rules with head A, by the supremum property, we have that ϑ&i Tk−1 P()(Bj)≤Tk P()(A) Therefore, by hypothesis, we obtain the following strict inequality ϑ&i Tk−1 P()(@j[gi 1(Di 1),...,gi si(Di si), Ci 1,...,Ci mi])< <ϑ&i Tk P()(@j[gi 1(Di 1),...,gi si(Di si), Ci 1,...,Ci mi]) Because all of the operators in this expression are monotonic, the strict inequality arises when at least one of the following two cases holds. 1. If j∈{1, ..., si}exists such that gi j( Tk−1 P()(Di j)) < gi j( Tk P()(Di j)) In this case, we straightforwardly obtain that |SA k| <|SA k+1|. 2. Otherwise, j∈{1, ..., mi}must exist such that Tk−1 P()(Ci j)<Tk P()(Ci j) 17 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.18 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• In this case, we can ensure that no finite operator is considered in the rules in PCi j. Therefore, by the induction hypothesis we have that the culprit collection for Tk P()(Ci j)is greater than that for Tk−1 P()(Ci j). Because this fact happens for all j∈{1, ..., mi}, if the rule riis not used in the culprit collection of some Tk P()(Ci j), then we can assert that the culprit collection for Tk+1 P()(A) will be greater than that for Tk P()(A). Thus, in this case, we obtain the result. Hence, it only remains to consider the case when the rule riis in the culprit collection of some Tk P()(Ci j), which will lead us to a contradiction. Therefore, we suppose that A ←iBj, ϑis in the culprit collection of Tk P()(Ci j). Hence, Ci j∈AntSet(A). Indeed, we can ensure that Aand Ci jare in the same spc-component of the associated range B-graph Hr P. Consequently, we have that the term Tm P()(A) must appear in the computation of Tk P()(Cj); that is, Tk P()(Ci j) = f[Tk P()(A)], where fis the composition by all operators and values recursively appearing in the iterations of TPon and Ci j, and it satisfies f[x] x, for all x∈L, because Aand Ci jare in the same spc-component and, by hypothesis, the operators of s-hyperparcs of the associated range B-graph satisfy Equation (1). Moreover, the aggregator @jalso satisfies this equation because it is the label of a s-hyperarc of the associated range B-graph. Therefore, the expression @j[ Tk P()(gi 1(Di 1)),...,  Tk P()(gi si(Di si)), T k P()(Ci 1),...,Tk P()(Ci j),...,Tk P()(Ci mi)] is equal to @j[ Tk P()(gi 1(Di 1)),...,  Tk P()(gi si(Di si)), T k P()(Ci 1),...,f[Tm P()(A)],...,Tk P()(Ci mi)] which implies that Tk+1 P()(A) Tm P()(A) because &iand @jsatisfy Equation (1). As a consequence of this inequality, the assumed strict inequality and the monotonicity of TP, we have the chain of inequalities Tm P()(A) Tk P()(A) ≺Tk+1 P()(A) Tm P()(A) which is a contradiction and finishes the proof.  Finally, the last termination theorem can be proven. Theorem 37. Given a multi-adjoint -algebra Land a multi-adjoint logic program Pwith finite dependences. If the shyperarcs of the associated range B-graph correspond to rules with an aggregator in the body satisfying Equation (1), and for every iteration nand propositional symbol A, the set of relevant values for Awith respect to Tn P()is a singleton, then TPterminates for every query. Proof. For every propositional symbol A, we have that the cardinals |SA n|cannot infinitely increase, due to the finitude of the operators gj lin G(PA). Moreover, the culprit collections for Ain each iteration are finite because the program has finite dependences. Thus, by Lemma 36, the iteration of TPmust reach the least fixed point in a finite number of steps; that is, TPterminates for every query.  An immediate consequence of the last result is its consideration on the unit interval, which also highlights its usefulness. Corollary 38. If the -algebra is defined on [0, 1], and the s-hyperarcs of the associated range B-graph correspond to rules with an aggregator in the body satisfy Equation (1), then TPterminates for every query. This last theorem makes the hypotheses of previous termination results more flexible, thus increasing the applicability scope. For example, it can be applied to the program in Example 32, obtaining that TPterminates for every query, unlike Theorem 30. 18 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.19 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• 5. Conclusions and future work We have shown that labeled directed hypergraphs capture more information from a program than graphs, indeed the original program can be recovered from this hypergraph. Hence, this new representation allows the use of hypergraph theory in logic programming. Therefore, hypergraphs provide a valuable representation of multi-adjoint logic programs, which both facilitates visualizing and also contains all of the information associated with the structure of these symbolically rich programs. For example, it has offered the possibility of generalizing the most important termination theorems given in [20] because it is not possible to directly apply the result in the aforementioned paper. For instance, it would be necessary to prove in any case Theorem 29. Moreover, Theorems 28 and 37 in [20] require programs with respect to local multi-adjoint -algebras. Hence, the rules of the original program must be adapted to new ‘subprograms’ that satisfy the properties and it must be proven that the new programs are semantically equivalent to the original, among other requirements. With consideration of hypergraphs, only the original program is required and the new results with more general hypotheses can be proven, which adapts the results in [20]. Specifically, the first termination theorem introduced in this paper allows the use of general aggregators in the programs when they are in s-hyperarcs of the associated B-graph. The second termination theorem supports the use of other family of operators with finite range. Consequently, the flexibility to model a database to know a priori the termination character of the obtained program is considerably improved, and so the number of applications in which the termination theorems can be used also is much broader. For example, they can be considered in many operational semantics given in fuzzy logic programming [19,37–39], due to the narrow relationship with the TPoperator. Hence, it is possible to know whether these computational procedures will finish for every query in advance. Moreover, the termination for every query can be studied independently by applying the termination theorems only to the subprogram PAand the associated subhypergraph HPA. In the future, this application will be studied in more depth for the most interesting operational semantics. Furthermore, the obtained results will be studied in other applications and more results will be analyzed. The consideration of directed hypergraphs has provided an extra level of representation of logic programs. We will use this relationship in other frameworks, such as for introducing new computational procedures for obtaining the least fixed point of a (multi-adjoint) logic program and to detect possible bottlenecks in the program. Other important goals will be to adapt the obtained termination results for handling negations in non-monotonic logic programming [13,14,46] and to be applied in first-order logic programming [17,19,28,36,39,50], which will allow us to increase the range of possible applications even further. Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. References [1] P. Alimonti, E. Feuerstein, U. Nanni, Linear time algorithms for liveness and boundedness in conflict-free Petri nets, in: Proceedings of the 1st Latin American Symposium on Theoretical Informatics, LATIN ’92, Springer-Verlag, Berlin, Heidelberg, 1992, pp. 1–14. [2] X. Allamigeon, On the complexity of strongly connected components in directed hypergraphs, Algorithmica 69 (2) (Jun 2014) 335–369. [3] G. Ausiello, A. D’Atri, D. Saccà, Minimal Representations of Directed Hypergraphs and Their Application to Database Design, Springer Vienna, Vienna, 1984, pp. 125–157. [4] G. Ausiello, R. Giaccio, G.F. Italiano, U. Nanni, Optimal traversal of directed hypergraphs, Technical report International Computer Science Institute, UC Berkeley, 1992. [5] G. Ausiello, G.F. Italiano, On-line algorithms for polynomially solvable satisfiability problems, J. Log. Program. 10 (1) (1991) 69–90. [6] G. Ausiello, L. Laura, Directed hypergraphs: introduction and fundamental algorithms—a survey, Theor. Comput. Sci. 658 (PB) (2017) 293–306. [7] G. Ausiello, M.G. Scutellà, Directed hypergraphs as a modelling paradigm, Riv. AMASES 21 (1–2) (1998) 97–123. [8] D. Azzolini, F. Riguzzi, E. Lamma, Studying transaction fees in the bitcoin blockchain with probabilistic logic programming, Information 10 (11) (2019). [9] A. B˘ adic˘ a, C. B˘ adic˘ a, M. Ivanovi´ c, D. Logof˘ atu, Exploring the space of block structured scheduling processes using constraint logic programming, in: I. Kotenko, C. Badica, V. Desnitsky, D. El Baz, M. Ivanovic (Eds.), Intelligent Distributed Computing XIII, Springer International Publishing, Cham, 2020, pp. 149–159. [10] C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985. 19 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.20 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• [11] V. Chandru, C.R. Coullard, P.L. Hammer, M. Montañez, X. Sun, On renamable Horn and generalized Horn functions, Ann. Math. Artif. Intell. 1 (1990) 33–48. [12] M.E. Cornejo, D. Lobo, J. Medina, Characterizing fuzzy y-models in multi-adjoint normal logic programming, in: J. Medina, M. Ojeda- Aciego, J.L. Verdegay, I. Perfilieva, B. Bouchon-Meunier, R.R. Yager (Eds.), Information Processing and Management of Uncertainty in Knowledge-Based Systems. Applications, Springer International Publishing, Cham, 2018, pp. 541–552. [13] M.E. Cornejo, D. Lobo, J. Medina, Syntax and semantics of multi-adjoint normal logic programming, Fuzzy Sets Syst. 345 (2018) 41–62. [14] M.E. Cornejo, D. Lobo, J. Medina, Relating multi-adjoint normal logic programs to core fuzzy answer set programs from a semantical approach, Mathematics 8(6) (2020) 881. [15] M.E. Cornejo, D. Lobo, J. Medina, Extended multi-adjoint logic programming, Fuzzy Sets Syst. 388 (2020) 124–145. [16] M.E. Cornejo, J. Medina, E. Ramírez-Poussa, A comparative study of adjoint triples, Fuzzy Sets Syst. 211 (2013) 1–14. [17] M.E. Cornejo, J. Medina Moreno, C. Rubio-Manzano, Towards a full fuzzy unification in the Bousi prolog system, in: 2018 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), 2018, pp. 1–7. [18] C. Damásio, J. Medina, M. Ojeda-Aciego, Sorted Multi-Adjoint Logic Programs: Termination Results and Applications, Lecture Notes in Artificial Intelligence, vol. 3229, 2004, pp. 252–265. [19] C. Damásio, J. Medina, M. Ojeda-Aciego, A tabulation procedure for first-order residuated logic programs: soundness, completeness and optimisations, in: Proc. FUZZ-IEEE 2006, in: IEEE Congress on Computational Intelligence (section Fuzzy Systems), 2006, pp. 9576–9583. [20] C. Damásio, J. Medina, M. Ojeda-Aciego, Termination of logic programs with imperfect information: applications and query procedure, J. Appl. Log. 5 (2007) 435–458. [21] C.V. Damásio, L.M. Pereira, Monotonic and residuated logic programs, in: Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU’01, in: Lecture Notes in Artificial Intelligence, vol. 2143, 2001, pp. 748–759. [22] C.V. Damásio, L.M. Pereira, Termination results for sorted multi-adjoint logic programming, in: Information Processing and Management of Uncertainty for Knowledge-Based Systems, IPMU?04, 2004, pp. 1879–1886. [23] M. Dekhtyar, A. Dekhtyar, V. Subrahmanian, Hybrid probabilistic programs: algorithms and complexity, in: Proc. of 1999 Conference on Uncertainty in AI, 1999. [24] A. del Val, On 2-SAT and renamable Horn, in: Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, AAAI Press/The MIT Press, 2000, pp. 279–284. [25] J.C. Díaz-Moreno, J. Medina, J.R. Portillo, Towards the use of hypergraphs in multi-adjoint logic programming, Stud. Comput. Intell. 796 (2019) 53–59. [26] W.F. Dowling, J.H. Gallier, Linear-time algorithms for testing the satisfiability of propositional Horn formulae, J. Log. Program. 1(3) (1984) 267–284. [27] M.v. Emden, R. Kowalski, The semantics of predicate logic as a programming language, J. ACM 23 (4) (1976) 733–742. [28] F. Formato, G. Gerla, M. Sessa, Similarity-based unification, Fundam. Inform. 41 (4) (2000) 393–414. [29] A. Frank, T. Király, Z. Király, On the orientation of graphs and hypergraphs, in: Submodularity, Discrete Appl. Math. 131 (2) (2003) 385–400. [30] G. Gallo, G. Longo, S. Pallottino, S. Nguyen, Directed hypergraphs and applications, Discrete Appl. Math. 42 (2–3) (apr 1993) 177–201. [31] G. Gallo, D. Pretolani, A new algorithm for the propositional satisfiability problem, Discrete Appl. Math. 60 (1) (1995) 159–179. [32] G. Gallo, G. Urbani, Algorithms for testing the satisfiability of propositional formulae, J. Log. Program. 7(1) (1989) 45–61. [33] F. Harary, Graph Theory, Addison-Wesley Series in Mathematics, Addison Wesley, 1969. [34] R.G. Jeroslow, R.K. Martin, R.L. Rardin, J. Wang, Gainfree Leontief substitution flow problems, Math. Program. 57 (1992) 375–414. [35] P. Julián-Iranzo, J. Medina, M. Ojeda-Aciego, On reductants in the framework of multi-adjoint logic programming, Fuzzy Sets Syst. 317 (2017) 27–43. [36] P. Julián, G. Moreno, J. Penabad, On fuzzy unfolding: a multi-adjoint approach, Fuzzy Sets Syst. 154 (1) (2005) 16–33. [37] P. Julián-Iranzo, J. Medina, P.J. Morcillo, G. Moreno, M. Ojeda-Aciego, An Unfolding-Based Preprocess for Reinforcing Thresholds in Fuzzy Tabulation, Lecture Notes in Computer Science, vol. 7902, 2013, pp. 647–655. [38] P. Julián-Iranzo, J. Medina, G. Moreno, M. Ojeda-Aciego, Thresholded tabulation in a fuzzy logic setting, Electron. Notes Theor. Comput. Sci. 248 (2009) 115–130. [39] P. Julián-Iranzo, G. Moreno, J. Penabad, Thresholded semantic framework for a fully integrated fuzzy logic language, J. Log. Algebraic Methods Program. 93 (2017) 42–67. [40] H. Karimi, A. Kamandi, A learning-based ontology alignment approach using inductive logic programming, Expert Syst. Appl. 125 (2019) 412–424. [41] M. Kifer, V.S. Subrahmanian, Theory of generalized annotated logic programming and its applications, J. Log. Program. 12 (1992) 335–367. [42] D. Klein, C.D. Manning, Parsing and hypergraphs, in: Proceedings of the Seventh International Workshop on Parsing Technologies, Beijing, China, Oct. 2001, pp. 123–134. [43] T. Kuhr, V. Vychodil, Fuzzy logic programming reduced to reasoning with attribute implications, Fuzzy Sets Syst. 262 (2015) 1–20, Theme: Logic and Computer Science. [44] L.V.S. Lakshmanan, F. Sadri, On a theory of probabilistic deductive databases, Theory Pract. Log. Program. 1(1) (2001) 5–42. [45] J. Lloyd, Foundations of Logic Programming, Springer Verlag, 1987. [46] N. Madrid, M. Ojeda-Aciego, On the existence and unicity of stable models in normal residuated logic programs, Int. J. Comput. Math. 89 (3) (2012) 310–324. [47] S.L. Marcin Suszy´ nski, Jan Žurek, Modelling of assembly sequences using hypergraph and directed graph, Tehn. Vjesnik 21 (2014) 1229–1233. [48] J. Medina, M. Ojeda-Aciego, A. Valverde, P. Vojtáš, Towards Biresiduated Multi-Adjoint Logic Programming, Lecture Notes in Artificial Intelligence, vol. 3040, 2004, pp. 608–617. 20 JID:FSS AID:8242 /FLA [m3SC+; v1.352] P.21 (1-21) J.C. Díaz-Moreno, J. Medina and J.R. Portillo Fuzzy Sets and Systems ••• (••••)•••–••• [49] J. Medina, M. Ojeda-Aciego, P. Vojtáš, Multi-adjoint logic programming with continuous semantics, in: Logic Programming and Non- Monotonic Reasoning, LPNMR’01, in: Lecture Notes in Artificial Intelligence, vol. 2173, 2001, pp. 351–364. [50] J. Medina, M. Ojeda-Aciego, P. Vojtáš, Similarity-based unification: a multi-adjoint approach, Fuzzy Sets Syst. 146 (2004) 43–62. [51] N.J. Nilsson, Principles of Artificial Intelligence, Morgan Kaufmann, San Francisco (CA), 1980. [52] L. Paulík, Best Possible Answer is Computable for SLD-Resolution, Lecture Notes in Logic, vol. 6, 1996, pp. 257–266. [53] D. Pretolani, Satisfiability and Hypergraphs, PhD thesis, Università di Pisa, 1993. [54] D. Pretolani, A directed hypergraph model for random time dependent shortest paths, Eur. J. Oper. Res. 123 (1998) 315–324. [55] F. Sáenz-Pérez, Applying constraint logic programming to SQL semantic analysis, Theory Pract. Log. Program. 19 (5–6) (2019) 808–825. [56] J. Schlipf, F. Annexstein, J. Franco, R. Swaminathan, On finding solutions for extended Horn formulas, Inf. Process. Lett. 54 (3) (1995) 133–137. [57] M.G. Scutella, A note on Dowling and Gallier’s top-down algorithm for propositional Horn satisfiability, J. Log. Program. 8(3) (1990) 265–273. [58] Y. Tadesse, Using edge-induced and vertex-induced subhypergraph polynomials, Math. Scand. 117 (2) (2015) 161–169. [59] A. Tarski, A lattice-theoretical fixpoint theorem and its applications, Pac. J. Math. 5(2) (1955) 285–309. [60] M. Thakur, R. Tripathi, Linear connectivity problems in directed hypergraphs, Theor. Comput. Sci. 410 (27) (2009) 2592–2618. [61] A. Torres, J. Araoz, Combinatorial models for searching in knowledge bases, Acta Cient. Venez. 39 (1988) 387–394. [62] J.D. Ullman, Principles of Database Systems, 2nd edition, W. H. Freeman & Co., USA, 1983. [63] A.V. Zeigarnik, O.N. Temkin, D. Bonchev, Chemical Reaction Networks: A Graph-Theoretical Approach, CRC Press, 1996. 21