Sufficient and necessary conditions for solution finding in valuation-based systems

Sufficient and necessary conditions for Dynamic Programming in Valuation-Based Systems. Jordi Roca-Lacostena1, Jesus Cerquides1, Marc Pouly2 Abstract Valuation algebras abstract a large number of formalisms for automated reasoning and enable the definition of generic inference procedures. Many of these formalisms provide some notion of solution. Typical examples are satisfying assignments in constraint systems, models in logics or solutions to linear equation systems. Many widely used dynamic programming algorithms for optimization problems rely on low treewidth decompositions and can be understood as particular cases of a single algorithmic scheme for finding solutions in a valuation algebra. The most encompassing description of this algorithmic scheme to date has been proposed by Pouly and Kohlas together with sufficient conditions for its correctness. Unfortunately, the formalization relies on a theorem for which we provide counterexamples. In spite of that, the mainline of Pouly and Kohlas’ theory is correct, although some of the necessary conditions have to be revised. In this paper we analyze the impact that the counter-examples have on the theory, and rebuild the theory providing correct sufficient conditions for the algorithms. Furthermore, we also provide necessary conditions for the algorithms, allowing for a sharper characterization of when the algorithmic scheme can be applied. 1. Introduction Solving optimization problems is an important and well-studied task in computer science. There are many optimization problems whose solution can be expressed as an assignment of values to a set of variables. Usually, the larger the number of variables involved in the problem, the more complex it is to find a solution. A particular approach to tackle problems whose solution involves a large number of variables is known as dynamic programming [1] and can be found in almost every handbook about algorithms and programming techniques [8, 26]. Email addresses: [email protected] (Jordi Roca-Lacostena), [email protected] (Jesus Cerquides), [email protected] (Marc Pouly) 1IIIA-CSIC, Campus UAB, 08193 Cerdanyola, Spain 2Lucerne University of Applied Sciences and Arts, Technikumstrasse 21, 6048 Horw, Switzerland Preprint submitted to Elsevier May 3, 2019 arXiv:1508.03523v1 [cs.AI] 14 Aug 2015 The initial works of Bellman and Dreyfus [1, 2] studied the problem from a decision making perspective and used the term optimal policy instead of solution and decision instead of variable. They advocated solving the problem by performing a sequence of steps, which they associated with an artificial timelike property, hence the name dynamic. At each step, the values for some of the variables were determined, based on the values determined in the previous steps. These works establish the basis of serial dynamic programming. In order to understand when such a technique could be applied, Bellman enunciated the Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. Different formalizations of the principle have been proposed. Karp and Held [16] concentrate on the sequential nature of dynamic programming. Non-serial dynamic programming is introduced later, among others, by Bertelè and Brioschi [3, 12]. Helman [14] formalizes a wider view of dynamic programming based on the idea of computationally feasible dominance relations. This formalization is later reformulated in a categorical setting by Bird and de Moor [4] and successfully translated into a generic program3[9, 10]. More recently, Lew and Mauch [20] proposed a formalization that takes as central object the dynamic programming functional equation, which can be automatically translated into efficient code. Also, Sniedovich [27, 28] explored the fundations of dynamic programming presenting a “recipe” and formally defining adecomposition scheme as the key concept for dynamic programming. Hovewer, in each of these later works, dynamic programming is presented as an algorithm that can be applied to optimize functions taking values in the real numbers. Some of the later research [7, 15] is concerned with finding more constrained models for dynamic programming, which enable the finding of limitations for dynamic programming solutions. In a parallel and more algebraic path of research lies the approach taken by Mitten [21] and further generalized by Shenoy [25], for functions taking values in any ordered set ∆. Shenoy introduces a set of axioms that later on will be known as valuation algebras. In those terms, Shenoy is the first to connect the concept of solution with the projection operation of the valuation algebra. In a further generalization effort, Pouly and Kohlas [23, 22] drop the assumption that valuations are functions that map tuples into a value set ∆.They introduce three different algorithms, that we have named Extend-To-GlobalProjection,Extend-To-Subtree and Single-Extend-To-Subtree and provide sufficient conditions for their correctness. Pouly and Kohlas’ algorithms are more general than their predecessors in the literature. This increased gen3Here we refer to the generic programming idea of Dehnert and Stepanov [11, 29] of trying to provide algorithms that work in the most general setting without loss of efficiency. 2 erality comes at no computational cost, since when applied in the previously covered scenarios, their particularization coincides exactly with the previously proposed algorithm. Furthermore, by dropping the assumption that valuations are functions, their algorithms can be applied to previously uncovered cases such as the solution of linear equation systems or the algebraic path problem[31]. Against this background, in this paper we establish by means of counterexamples that, unfortunately, one of the fundamental theorems in Pouly and Kohlas’ theory is incorrect. Since the theorem is used in the proofs of several other results in their work, uncertainty spreads over the truth of these now potentially falsable results. In the paper we analyze the impact on the theory and clarify which statements were true but incorrectly proven and which of them were false. For the true ones, we provide a correct proof whilst for the false ones we identify the additional conditions required for their correctness. The contribution of the paper is not limited to correcting Pouly and Kohlas’ theory. We do introduce two new concepts: projective completability and piecewise completability. We show that projective completability is a sufficient condition for the Extend-To-Global-Projection algorithm, whereas piecewise completability is a sufficient condition for the Extend-To-Subtree algorithm. Furthermore, we do also show that they are a necessary condition. To the best of our knowledge, this is the first time in which necessary conditions for dynamic programming algorithms on valuation-based systems are identified. A particularly relevant subfamily of valuation algebras, known as semiring induced valuation algebras [17], underlie the foundation of many important artificial intelligence formalisms such as constraint systems, probability potentials for Bayesian networks or Spohn potentials. Many optimization problems can be formalized by means of the valuation algebra induced by a selective conmutative semiring. We revise the sufficient conditions (defined in terms of properties of the semiring) proposed by Pouly and Kohlas [23, 22], and provide correct sufficient conditions for each of the algorihtms. Furthermore, where possible we also provide necessary conditions. The paper is structured as follows. In section 2 we review valuation algebras, covering join trees and the basic algorithms for assessing one projection (Collect) and several projections (Collect+Distribute) of a factorized valuation. After that, in section 3 we present the solution finding problem, the abstract problem underlying optimization problems, and we show by means of counterexamples that one of the results in Pouly and Kohlas’ work is not correct. Later, in section 4 we analyze why disproving the result has a deep impact on the theory. As a consequence, in section 5 we identify new sufficient conditions for the algorithms. Furthermore, we prove that these conditions are also necessary. Since our conditions are weaker, we can use them to provide new proofs for the results in Pouly and Kohlas’ theory affected by the counterexamples. Then, in section 6, we study the specific case of semiring induced valuation algebras and provide sufficient and necessary conditions there in terms of properties of the semiring. Finally, we conclude in section 7. 3 2. Background In this section we start by defining valuation algebras. Later on, we introduce the problem of assessing the projection of a factorized valuation and review the Collect algorithm to solve that problem. Finally we review the algorithm used to assess multiple projections of a factorized valuation. 2.1. Valuation algebras The basic elements of a valuation algebra are so-called valuations, that we subsequently denote by lower-case Greek letters such as φor ψ. Let Φbe a set of valuations and U={u1, u2, . . . , u|U|}be a finite set of variables. A valuation algebra (Φ, U)has three operations: 1. Labeling: Φ→ P(U); φ7→ d(φ), 2. Combination: Φ×Φ→Φ; (φ, ψ)7→ φ×ψ, 3. Projection: Φ× P(U)→Φ; (φ, X)7→ φ↓Xfor X⊆d(φ). satisfying the following axioms: A1 Commutative semigroup:Φis associative and commutative under ×. A2 Labeling: For ψ, φ ∈Φ, d(φ×ψ) = d(φ)∪d(ψ). A3 Projection: For φ∈Φ,and X⊆d(φ), d(φ↓X) = X. A4 Transitivity: For φ∈Φand X⊆Y⊆d(φ),(φ↓Y)↓X=φ↓X. A5 Combination: For φ, ψ ∈Φwith d(φ) = X,d(ψ) = Y, and Z∈ P(U)such that X⊆Z⊆X∪Y, (ψ×φ)↓Z=φ×ψ↓(Z∩Y). A6 Domain: For φ∈Φwith d(φ) = X, φ↓X=φ. We say that a valuation e∈Φis an identity valuation provided that d(e) = ∅ and φ×e=φfor each φ∈Φ.As proven in [19], any valuation algebra that does not have and identity valuation can easily be extended to have one. In the following and without loss of generality we assume that our valuation algebra has an identity valuation e. Let Γ = {γ1, . . . , γn}be a set of valuations. We define Qγ∈Γγas e×γ1× · · · × γn. Definition 1. Let Ube a finite set of variables and let Didenote the domain of variable ui,i.e. the set of its possible values. Define further D=S|U| i=1 Di. A tuple xwith domain X∈ P(U)is a map x:X→Dsuch that x(ui)∈Difor all ui∈X. Let ΩXdenote the set of all tuples with domain Xif X6=∅and set Ω∅={} where is introduced for convenience and can be understood as the empty tuple. We denote the set of all tuples as Ω = SX∈P(U)ΩX.A pair hU, Ωi is known as a variable system. Three basic operations are defined on tuples: 4 1. Labeling: Ω→ P(U);x7→ d(x)such that d(x) = Xif and only if x∈ΩX. 2. Projection: Ω× P(U)→Ω;(x, Y )7→ x↓Y, defined when Y⊆d(x), where x↓Yis a tuple with domain Ydefined as x↓Y(ui) = x(ui)for any ui∈Y if Y6=∅and x↓∅ =. 3. Concatenation: Ω×Ω→Ω;(x,y)7→ hx,yi,defined when x↓d(x)∩d(y)= y↓d(x)∩d(y), where z=hx,yiis a tuple with domain d(x)∪d(y)such that z(ui) = (x(ui)if ui∈d(x) y(ui)otherwise. Note that, although sharing the same name, the labeling and projection operations on tuples are not connected to the equivalently named operations defined on valuations. We illustrate the previous concepts with an example of valuation algebra. Example 1. Let Ube a finite set of binary variables (that is, for each ui∈U, Di={0,1}). The set of valuations Φis composed of all the functions φ: ΩX→ {0,1}, where X⊆U. The labeling operation is defined by d(φ) = X. The combination of two valuations φ, ψ is the valuation (φ×ψ)(x) = φ(x↓d(φ))· ψ(x↓d(ψ)),where ·is the boolean product. The projection of a valuation φwith d(φ) = Xto a domain Y⊆Xis the valuation φ↓Y(y) = max z∈ΩX−Yφ(hy,zi). As proven in [18] this valuation algebra of indicator functions satisfies axioms A1-A6. In this paper we will be interested in valuation algebras with a variable system. Some relevant examples are relational algebra, which is fundamental to databases, the algebra of probability potentials, which underlies many results in probabilistic graphical models and the more abstract class of semiring induced valuation algebras [17, 23]. 2.2. Assessing the projection of a factorized valuation A relevant problem in many valuation algebras is the problem of assessing the projection of a factorized valuation. Problem 1. Let (Φ, U)be a valuation algebra, φ1, . . . , φnbe valuations in Φ, and X⊆d(φ1)∪ · · · ∪ d(φn). Assess (φ1× · · · × φn)↓X. Note that when our valuations are probability potentials, this is the well studied problem of assessing the marginal of a factorized distribution, also known as Markov Random Field. The Fusion algorithm [24] (a.k.a. variable elimination) or the Collect algorithm (a.k.a. junction tree or cluster tree algorithm)[23, 22] can be used to assess projections of factorized valuations. Since our results build on top of the Collect algorithm, we provide a more accurate description below. A necessary condition to run the Collect algorithm is organizing the valuations φ1, . . . , φninto a covering join tree, which we introduce after some basic definitions. 5 An undirected graph is a pair (V, E),where Vis a set of nodes and a E⊆ {{i, j}|i∈V, j ∈V}is a set of edges. The set of neighbors of a node iis ne(i) = {j|{i, j} ∈ E}.Atree is a undirected connected graph without loops. Alabeled tree is any tree (V, E)together with a function λ:V→ P(U)that links each node with a single domain in P(U). A join tree is a labeled tree T= (V, E, λ, U)such that for any i, j ∈Vit holds that λ(i)∩λ(j)⊆λ(k)for all nodes kon the path between iand j. In that case, we say that Tsatisfies the running intersection property. For each edge {i, j} ∈ E, we define the separator between iand jas sij =λ(i)∩λ(j). Definition 2. Given a valuation φthat factorizes as φ=φ1× · ·· × φn,we say that a join tree T= (V, E, λ, U)is a covering join tree for this factorization if for all φjthere is a node i∈Vsuch that d(φj)⊆λ(i). In that case it is always possible to define a valuation assignment, that is a function a:{1,...n} → V, such that for all j∈ {1, . . . , n}, d(φj)⊆λ(a(j)), that assigns each valuation to one and only one of the nodes in the tree. Thus, given a node j, a−1(j) stands for the set of valuations which are assigned to node j. For each node i in the covering join tree we define ψi=Qj∈a−1(i)φj.Note that φfactorizes as φ=Qi∈Vψi. The complexity of each of the algorithms presented in the paper increases with the cardinality of λ(i).Thus we want our sets λ(i)to be as small as possible. In this work we will make the assumption that the covering join trees are minimally labelled. Assumption 1. The nodes in a covering join tree are minimally labeled, that is for each i∈V, and for each k∈ne(i) λ(i) = d(ψi)∪[ j∈ne(i)−{k} sij.(1) Intuitively, the assumption means that the scope of a node does not contain unnecessary variables. Note that given a tree and a valuation assignment a, there is an easy way4to assess a minimally labelled covering join tree. Since, the so assessed tree leads to smaller costs for the algorithms, the assumption can be considered to be without loss of generality from a practical point of view and simplifies the proofs. Definition 3. Arooted join tree is a join tree where one of the nodes has been designated as root. Let ibe a node in a rooted join tree whose root is r. The parent of a node i,piis the node directly connected to it on the path to the root. Every node except the root has a unique parent. The separator of i, siis defined as si=(∅if i=r sipiotherwise . 4See appendix B for more details 6 Algorithm 1 Collect algorithm 1: for all nodes iof Tdo 2: ψi:= Qj∈a−1(i)φj 3: ψ0 i:= ψi 4: end for 5: for all nodes iof Texcept the root in an upward order do 6: µi→pi:= ψ0 i ↓si 7: ψ0 pi:= ψ0 pi×µi→pi 8: end for 9: return Ψ,Ψ0,µwhere Ψ = {ψi|i∈V},Ψ0={ψ0 i|i∈V},µ={µi→pi|i∈V− {r}} We note ch(i), the set containing the children of i(those nodes whose parent is i), de(i)the set containing the descendants of i(those nodes that have iin their path to the root), and nde(i)as the set containing those nodes of Twhich are not descendants of i, namely nde(i) = V\(de(i)∪ {i}). Definition 4. Let I=hi1, . . . ,inibe an ordering of the nodes of the rooted tree T.We say that Iis upward if every node appears after all of its children. We say that Iis downward if every node appears before any of its children. Algorithm 1 provides a description of the Collect algorithm. It is based on sending messages upwards, through the edges of the covering join tree, until the root node is reached. The message µi→pisent from node ito its parent summarizes the information in the subtree rooted at iwhich is relevant to its parent. The running intersection property guarantees that no information is lost. Theorem 1. After running Algorithm 1 (Collect) over the nodes of a rooted covering join tree for φ=Qkφk, we have that ψ0 i= (ψi×Qj∈de(i)ψj)↓λ(i). In particular, if ris the root ψ0 r=φ↓λ(r). The theorem is an adaptation of Theorem 3.6. in [23] where the proof can be found. As a consequence of this theorem, we can use the Collect algorithm to solve the projection problem provided that we are given a rooted covering join tree for the factorization we would like to project and that the set of variables Xwhich we want to project to is a subset of λ(r). 2.3. Assessing several projections of a factorized valuation Many times we are required to assess the projections of a single factorized valuation to different subsets of variables. The corresponding problem can be defined as follows Problem 2. Let (Φ, U)be a valuation algebra, φ1, . . . , φnbe valuations in Φ, and T= (V, E, λ, U)a rooted covering join tree for φ=Qkφk. For all i∈V, assess φ↓λ(i). The Collect+Distribute algorithm (Algorithm 2) shows how the result of the Collect algorithm can be used to assess the remaining projections by communicating messages down the tree. The next result shows that the Collect+Distribute algorithm can be used to solve problem 2. 7 Algorithm 2 Collect+Distribute algorithm 1: Ψ,Ψ0,µ←Collect(Φ,T) 2: for all nodes iof Texcept the root in a downward order do 3: µpi→i:= ψpi×Qj∈ne(pi)−{i}µj→pi↓si 4: ψ0 i:= ψ0 i×µpi→i 5: end for 6: return Ψ0; Theorem 2. After running the Collect+Distribute algorithm over the nodes of a rooted covering join tree for φ=Qkφk, we have that ψ0 i=φ↓λ(i). The theorem is a rewriting of Theorem 4.1 in [23] where the proof can be found. 3. Finding solutions in valuation algebras: definitions and counterexamples In the previous section we have shown that the Collect algorithm can be used to assess one projection and that the Collect+Distribute algorithm can be used when many projections are needed. In this section we focus on the solution finding problem (SFP). The problem is of foremost importance, since it lies at the foundation of dynamic programming [25, 3]. Furthermore, problems such as satisfiability, solving Maximum a Posteriori queries in a probabilistic graphical models, or maximum likelihood decoding are particular instances of the SFP. We start by formally defining the problem. Then we review the concept of family of configuration extension sets which lies the foundation of the theory of generic solutions described in [22, 23]. Unfortunately, although the inspirational ideas and algorithms underlying Pouly and Kohlas’ work are correct, their formal development is not. Thus, we end up the section providing two counter examples to one of their fundamental theorems. 3.1. The solution finding problem Up to now, the most general formalization of the SFP is the one provided by [25] and adapted by Pouly and Kohlas to the formal framework of valuation algebras in Chapter 8 of [23]. As in the projection assessment problem, in the SFP we are given a set of valuations φ1, . . . , φn∈Φas input. However, instead of a projection of its combination φ=φ1×. . . ×φn, we are required to provide a tuple xwith domain d(φ), such that xis a solution for φ. To give a proper sense to the previous sentence we need to define the meaning of “being a solution”. The most general way in which we can do this is by defining a family c={cφ|φ∈Φ}of solution sets. For each valuation φ∈Φ, the solution set cφ⊆Ωd(φ). Now, xis considered a solution for φif and only if x∈cφ.We say that the family of sets cis a solution concept. Now we can formally define the SFP as follows 8 Problem 3 (Solution Finding Problem (SFP)).Given a valuation algebra (Φ, U), a variable system hU, Ωi,a solution concept c, and a set of valuations φ1, . . . , φn∈Φ,the single SFP requests to find any x∈Ωd(φ)such that xis a solution for φ=φ1×. . . ×φn.The partial SFP receives the same input and requests to assess a subset of the set of solutions cφ. The complete SFP receives the same input and requests to assess the full set of solutions cφ. 3.2. Solving the solution finding problem by completing partial solutions Finding a solution to a big problem using dynamic programming amounts to (1) breaking it into smaller problems, (2) start from an empty solution, and (3) progressively complete this partial solution so that it solves each of the smaller problems. Since we assume the existence of a variable system, the empty solution will have no value assigned to any variable. Then, each subproblem solved will complete the partial solution by assigning values to some of the unassigned variables. After the process is finished, all variables have a value assigned and this complete assignment is a solution. In their works in 2011, Pouly and Kohlas [23, 22] provide a formal foundation to dynamic programming. They present several algorithmic schemas, and characterize the sufficient conditions for their correctness. Their algorithms can be applied to previously uncovered dynamic programming applications, such as solving systems of linear equations. The most exhaustive presentation of Pouly and Kohlas’ theory is done in [23]. We refer to that text as PK. For example we use “Lemma PK8.1” to refer to Lemma 8.1 in [23]. To formalize the process of completing a partial solution, they introduce sets of extensions. Intuitively, given a tuple xwith domain Xand a valuation φ, the set of extensions of xto φ,WX φ(x)contains those tuples that we can concatenate to xto obtain a solution of φ. We say that yis an extension of x to φwhenever y∈WX φ(x).Following that, the set of extension W∅ φ()contains tuples which are solutions of φ, that is W∅ φ()⊆cφ.Although for solving the single and partial SFP it could be useful that W∅ φ()(cφ,in this work we assume (with no impact on the results presented) that W∅ φ() = cφ.If we define c↓X φ={y↓X|y∈cφ}, Lemma PK8.1 proves that cφ↓X=c↓X φ.To simplify notation, we will always use cφ↓X. We can constitute a family Wcontaining a set of extensions WX φ(x),for each φ∈Φ, each X⊆d(φ)and each x∈ΩX. In order for their algorithms to work Pouly and Kohlas’ impose a condition on this family, that basically states that every extension can be calculated in two steps. Namely that for each φ∈Φ, for each X⊆Y⊆d(φ)and for each x∈cφ↓X, we have that zis an extension of xto φiff z↓Y−Xis an extension of xto φ↓Y, and z↓d(φ)−Yis an extension of hx,z↓Y−Xito φ. More formally, 9 i pi λde(i) λnde(i) X si Figure 1: Visualizing the decomposition lemma cient and necessary condition for algorithm Extend-To-Global-Projection to find all solutions. After that we study how piecewise completability determines the correctness of the Extend-To-Subtree and Single-Extend-ToSubtree algorithms. We close the section by explaining how those result in [23] which were correct can be proven from the results presented here. 5.1. The covering join tree decomposition lemma Our first objective is to characterize subsets of valuations which are well behaved with respect of the operations of the valuation algebra. Definition 7. A subset of valuations Ξ⊆Φis projection-closed if for each φ∈ Ξ,and each X⊆d(φ),φ↓X∈Ξ. A subset of valuations Ξ⊆Φis combinationbreakable if for each φ∈Ξ, such that φ=ξ1×ξ2,we have that both ξ1, ξ2∈Ξ. If a subset of valuations is projection-closed we can safely project a valuation in the subset and we know we will get another valuation in the subset. A subset of valuations is combination-breakable if whenever we can factorize a valuation in the subset as a combination of two other valuations we know that each of the components is guaranteed to be in the subset. Note that this does not imply that if we take two valuations from the subset its product will be in the subset. A trivial example of projection-closed and combination-breakable set of valuations is the set of all valuations Φ. Next, we introduce the main result of this section proving that for any node i∈Vin a join tree (V, E, λ, U)under reasonable conditions on X, we can express the projection (φ1× · · · × φn)↓(X∪λ(i)) as a product of two valuations, one of them with scope Xand the other one with scope λ(i). The conditions on Xare that it should cover the separator siand that all its variables should appear in the non-descendants of i. In order to formalize the condition for each node i∈V, we define λde(i)as the set of variables that appear in the scope of the descendants of i, namely λde(i) = Sj∈de(i)λ(j). Furthermore we define λnde(i)as the set of variables that appear in the scope of the nondescendants of i, namely λnde(i) = Sj∈nde(i)λ(j). Figure 1 shows Xin blue, 16 λde(i)in green and λnde(i)in red in a simple example to help understanding the notation and the conditions on the lemma. Lemma 1. Let (Φ, U)be a valuation algebra. Let Ξ⊆Φbe a subset of valuations projection-closed and combination-breakable. Let φ∈Ξ, φ =φ1×· · ·×φn. For any node iof T,and any domain X⊆λnde(i),such that si⊆X, we have that φ↓(X∪λ(i)) factorizes as φ↓(X∪λ(i)) =α×β, with α∈Ξ, d(α) = Xand β∈Ξ, d(β) = λ(i). Concretely α=Qj∈nde(i)ψj↓X and β=ψi×Qj∈de(i)ψj↓λ(i). Proof. From definition 2, we have that φ=Qi∈Vψi.We can factorize φas φ=η1×ψi×η2,where η1=Qj∈nde(i)ψjwith d(η1) = Sj∈nde(i)d(ψj)and η2=Qj∈de(i)ψj.By equation B.3 from the appendix, we have that d(η2) = λde(i). Applying the factorization we have that φ↓(X∪λ(i)) = (η1×ψi×η2)↓X∪λ(i). Since X⊆λnde(i), we have that X∪λ(i)⊆λnde(i)∪λ(i), and by axiom A4 φ↓(X∪λ(i)) =(η1×ψi×η2)↓λnde(i)∪λ(i)↓X∪λ(i). Now λnde(i)∪λ(i)covers both d(η1)and d(ψi)by the covering property, so we can apply axiom A5 to get φ↓(X∪λ(i)) =(η1×ψi)×η↓(λnde(i)∪λ(i))∩λde(i) 2↓X∪λ(i). Analyzing the domain where η2is projected to we find that λnde(i)∪λ(i)∩λde(i) = λnde(i)∩λde(i)∪λ(i)∩λde(i) =λ(i)∩λde(i)=[ j∈ch(i) sj where the first equality distributes the intersection, the second one applies that by equation A.3 from the appendix we know that λnde(i)∩λde(i)⊆λ(i)∩λde(i) and the third one uses equation A.2 also found at the appendix. Replacing in the expression above we get φ↓(X∪λ(i)) =η1×ψi×η↓Sj∈ch(i)sj 2↓X∪λ(i) . Since Sj∈ch(i)sj⊆λ(i)and d(ψi)⊆λ(i)we can apply again axiom A5, φ↓(X∪λ(i)) =η↓(X∪λ(i))∩d(η1) 1×(ψi×η↓Sj∈ch(i)sj 2). 17 From equation B.4 from the appendix, we have that d(η1) = λnde(i)and then φ↓(X∪λ(i)) =η↓(X∪λ(i))∩λnde(i) 1×ψi×η↓Sj∈ch(i)sj 2. Distributing the intersection, we have that (X∪λ(i))∩λnde(i)=(X∩λnde(i))∪ (λ(i)∩λnde(i)).In the lemma we required that X⊆λnde(i), and from here X∩λnde(i) = X. On the other hand by equation A.1, we have that si= (λ(i)∩λnde(i)) and since si⊆X, we get that φ↓(X∪λ(i)) =η↓X 1×ψi×η↓Sj∈ch(i)sj 2 and applying axiom A5 one last time, this time to join instead of to split, we get φ↓(X∪λ(i)) =η↓X 1×(ψi×η2)↓d(ψi)∪Sj∈ch(i)sj. Finally, by equation 1 we have that λ(i) = d(ψi)∪Sj∈ch(i)sj.So, we directly identify that φ↓X∪λ(i)factorizes as α×β, where α=η↓X 1and β= (ψi×η2)↓λ(i), with d(α) = Xand d(β) = λ(i). Note that since φ∈Ξ, and Ξis projection-closed, φ↓X∪λ(i)∈Ξ.Now, since φ↓X∪λ(i)=α×β, and Ξis combination-breakable we have that α∈Ξ,and β∈Ξ. 5.2. Completability properties of extension systems. In this section we define some properties which will allow us to characterize under which conditions the different algorithms work. Intuitively, these properties impose conditions under which the solution to a “simpler” problem can be completed to obtain a solution to a “more complex” problem. In this section, let (Φ, U)be a valuation algebra, Wa extension system and Ξ⊆Φbe a subset of valuations projection-closed and combination-breakable. Definition 8 (Projective completability).We say that projective completability (on products) holds on (Φ, U),W,and Ξif for each valuation φ∈Ξsuch that φ=ξ1×ξ2with domains d(ξ1) = Xand d(ξ2) = Yrespectively, for each configuration x∈cφ↓X, we have that each completion of xto φ↓Yis a solution of φ. That is, whenever CO(cφ↓X, φ↓Y)⊆cφ. Corollary 1. If projective completability holds on (Φ, U),W,and Ξ,then for each valuation φ∈Ξsuch that φ=ξ1×ξ2with domains d(ξ1) = Xand d(ξ2) = Y CO(cφ↓X, φ↓Y) = cφ. Proof. By definition of projective completability we have that CO(cφ↓X, φ↓Y)⊆ cφ. It only remains to prove that cφ⊆CO(cφ↓X, φ↓Y). Now, for any s∈cφand by applying equation 2 to cφ=W∅ φ()we have that s=hx,ziwhere x∈cφ↓Xand z∈WX φ(x).Since cφ↓Y=c↓Y φwe get 18 Y X ξ1 ξ2 φ=ξ1×ξ2 φ↓Y φ↓X x Take a solution Complete it hx,yi (a) Projective completion Y X ξ1 ξ2 φ=ξ1×ξ2 φ↓X x Take a solution Complete it hx,yi (b) Piecewise completion Figure 2: Process of building a solution by completion hx↓X∩Y,zi ∈ cφ↓Y.Note that x∈cφ↓Ximplies x↓X∩Y∈cφ↓X∩Y, and applying equation 2 to cφ↓Y=W∅ φ↓Y(),we get cφ↓Y={ht,zi|t∈cφ↓X∩Yand z∈WX∩Y φ↓Y(t)} we can conclude that z∈WX∩Y φ↓Y(x↓X∩Y), and hence that s∈CO(cφ↓X, φ↓Y). Definition 9 (Piecewise completability).We say that piecewise completability (on products) holds on (Φ, U),W,and Ξif for each valuation φ∈Ξ,such that φ=ξ1×ξ2, with domains Xand Yrespectively, and each x∈cφ↓X, each completion of xto ξ2is a solution of φor equivalently CO(cφ↓X, ξ2)⊆cφ. We say that piecewise completability is guaranteed non-empty if for each A such that ∅ 6=A⊆cφ↓X, we have that CO(A, ξ2)6=∅. Furthermore we say that piecewise completability is total if any solution can be obtained by piecewise completion, that is if CO(cφ↓X, ξ2) = cφ. 5.2.1. Classifying extension systems based on projective and piecewise completability In this section we investigate the relationship between piecewise and projective completability. Since the proofs for these results rely on valuation algebras on semirings, we only formulate the results here, leaving the proof to the appendix. 19 Proposition 1. There are valuation algebras and extension system satisfying: 1. neither projective nor piecewise completability, 2. projective completability but not piecewise completability, 3. piecewise completability but not projective completability, 4. both piecewise and projective completability. Proof. See appendix C 5.3. Necessary and sufficient condition for Extend-To-Global-Projection We start by seeing that the projective completability properties, required only for products of two valuations, can be extended to larger products by virtue of Lemma 1, as long as the conditions imposed by the lemma hold. Lemma 2. Assume projective completability holds on (Φ, D),W,and Ξ. Then, given φ=φ1× · · · × φn,and any rooted covering join tree T= (V, E, λ, U)for that factorization, for any node iof V, any domain X⊆λnde(i),such that si⊆X, we have that CO(cφ↓X, φ↓λ(i)) = cφ↓(X∪λ(i)) . Proof. We can apply Lemma 1 to get that φ↓(X∪λ(i)) =α×β, with d(α) = X and d(β)⊆λ(i).Then, we can apply Corollary 1 (with φ↓(X∪λ(i)) in the place of φand λ(i)in that of Y) getting CO(cφ↓X, φ↓λ(i)) = cφ↓(X∪λ(i)) . Now, we are ready to establish the sufficient condition for algorithm ExtendTo-Global-Projection, which is basically projective completability. Theorem 5. Let (Φ, U)be a valuation algebra, and Wa extension system. Let Ξ⊆Φbe a subset of valuations projection-closed and combination-breakable. Let φ∈Ξ,and Ta rooted covering join tree for a given factorization φ= φ1× · · · × φn.Let cbe the set of configurations assessed by algorithm ExtendTo-Global-Projection. If projective completability holds on Ξthen c=cφ. Proof. Take as loop invariant c=cφ↓Si∈V isited λ(i),where V isited is the set of nodes of the join tree that have been visited by the loop up to some point. At the beginning of the first iteration the invariant is satisfied, since c={} =cφ↓∅ . For the update of cthat is made at each interation, the conditions of Lemma 2 are satisfied, and hence, the lemma guarantees that if the invariant is true at the beginning of an iteration, it is true at the end. When the last iteration finishes, we have visited all the nodes and since d(φ) = ∪i∈Vλ(i)by Lemma 2, we have that c=cφ. In the first counterexample provided in section 3 we had CO(cφ↓X, φ↓Y) = ΩX∪Ywhereas cφ={(x7→ 0, y 7→ 0),(x7→ 1, y 7→ 1)}.Thus, projective completability does not hold in that counterexample and hence we do not have any guarantee that the algorithm will work. In the second counterexample as 20 the extension system is derived from this one, projective completability does not hold either. Therefore the misbehaviour of both counterexamples is correctly covered by the new result. In the next theorem we establish that projective completability is also a necessary condition, in the sense that, if for any product valuation, the algorithm is guaranteed to find a subset of its solutions, then projective completability must hold. Theorem 6. Let (Φ, U)be a valuation algebra, and Wa extension system. Let Ξ⊆Φbe a subset of valuations projection-closed and combination-breakable. If for each valuation φ∈Ξwhich factorizes as φ=ξ1×ξ2and for each rooted covering join tree T,Extend-To-Global-Projection assesses csuch that c⊆cφ,then projective completability holds on Ξ. Proof. Assume that Extend-To-Global-Projection always assesses a subset of cφ.For any φ∈Ξ, φ =ξ1×ξ2,with domains Xand Yrespectively, we define a covering join tree with two nodes: v1,with label λ(v1) = Xcovering ξ1, and its single child v2,with label λ(v2) = Ycovering ξ2.We can run ExtendTo-Global-Projection on T, assessing cwhich by our assumption will be a subset of cφ.By manual expansion of the expressions in the algorithm, we see that, for this small tree the solution set assessed is c=CO(CO({}, φ↓X), φ↓Y). Now, since cφ↓X=CO({}, φ↓X), we have that c=CO(cφ↓X, φ↓Y)and since we had that c⊆cφ,we have that CO(cφ↓X, φ↓Y)⊆cφ.Since this holds for any φ∈Ξ, φ =ξ1×ξ2,projective completability must hold. As noticed by the counterexamples provided in section 3 the necessary and sufficient conditions for the Extend-To-Global-Projection algorithms were not correctly understood in the former literature. We have provided a characterization of the subsets of a valuation algebra where the Extend-ToGlobal-Projection algorithm works by means of identifying a sufficient and necessary condition, namely projective completability. 5.4. Necessary and sufficient condition for Extend-To-Subtree As we did in the previous section, we start by seeing that piecewise completability properties, required only for products of two valuations, can be extended to larger products by virtue of Lemma 1, as long as the conditions imposed by the lemma hold. Lemma 3. Let (Φ, U)be a valuation algebra, and Wa extension system. Let Ξ⊆Φbe a subset of valuations projection-closed and combination-breakable. Then, for any φ∈Ξ,any rooted covering join tree Tfor a given factorization φ=φ1× · · · × φn,any node iof T,any domain X⊆λnde(i),such that si⊆X, and any set A⊆cφ↓X, we define β=ψi×Qj∈de(i)ψj↓λ(i)and we have that 1. If piecewise completability holds, then CO(A, β)⊆cφ↓(X∪λ(i)) , 2. If piecewise completability is guaranteed non-empty, then whenever A6=∅ we have that CO(A, β)6=∅. 21 3. If piecewise completability is complete we have that CO(cφ↓X, β) = cφ↓(X∪λ(i)) . Proof. We can apply Lemma 1 to get that φ↓(X∪λ(i)) =α×β, with d(α) = X, d(β) = λ(i),and β=ψi×Qj∈de(i)ψj↓λ(i).The conditions to apply piecewise completability hold (with φ↓(X∪λ(i)) in place of φand λ(i)in that of Y) getting that CO(A, β)⊆cφ↓(X∪λ(i)) .The second and third statements can be proven the same way. Following what we did with Extend-To-Global-Projection, now we are ready to establish the sufficient contitions for the Extend-To-Subtree algorithm, namely piecewise completability in its different flavors. Theorem 7. Let (Φ, U)be a valuation algebra, and Wa extension system. Let Ξ⊆Φbe a subset of valuations projection-closed and combination-breakable. Let φ∈Ξ,and Tbe a rooted covering join tree for a given factorization φ= φ1× · · · × φn.Let cbe the set of configurations assessed by algorithm ExtendTo-Subtree. We have that 1. If piecewise completability holds on Ξ, then cis a subset of cφ. 2. If piecewise completability is guaranteed non-empty on Ξthen also c6=∅. 3. If piecewise completability is total on Ξ, then c=cφ. Proof. To prove statement 1, take as loop invariant c⊆cφ↓Si∈V isited λ(i),where V isited is the set of nodes of the join tree that have been visited by the loop up to some point. At the beginning of the first iteration the invariant is satisfied, since c={} ⊆ cφ↓∅ .For the update of cthat is made at each interation, the conditions of Lemma 3 are satisfied, and hence, the lemma guarantees that if the invariant is true at the beginning of an iteration, it is true at the end. When the last iteration finishes, we have visited all the nodes and since Lemma 2 shows that d(φ) = ∪i∈Vλ(i),we have that c⊆cφ.Statements 2 and 3 can be proven the same way. Again, piecewise completability is not only a sufficient condition, but also necessary if the Extend-To-Subtree algorithm works in a consistent manner, as proven by the following theorem. Theorem 8. Let (Φ, U)be a valuation algebra, and Wa extension system. Let Ξ⊆Φbe a subset of valuations projection-closed and combination-breakable. If for each valuation φ∈Ξ, φ =ξ1×ξ2and for each rooted covering join tree T, Extend-To-Subtree assesses csuch that 1. c⊆cφ,then piecewise completability holds on Ξ. 2. ∅ 6=c⊆cφ,then piecewise completability is guaranteed non-empty on Ξ. 3. c=cφ,then piecewise completability is total on Ξ. 22 Proof. We start proving statement 1. Assume that Extend-To-Subtree always assesses a subset of cφ.Given φ∈Ξ, φ =ξ1×ξ2,with domains Xand Yrespectivelty, we define a join tree with two nodes: v1,with label λ(v1) = X covering ξ1,and its single child v2,with label λ(v2) = Ycovering ξ2.We can run Extend-To-Subtree-Projections on T, getting c⊆cφ.However in this particular case we can see that c=CO(CO({}, φ↓X), ξ2). Now, since cφ↓X=CO({}, φ↓X), we have that c=CO(cφ↓X, ξ2). Since the algorithm is guaranteed to return c⊆cφ,piecewise completability must hold. Statements 2 and 3 can be proven the same way. 5.5. Sufficient conditions for Single-Extend-To-Subtree Finally, we show that the Single-Extend-To-Subtree algorithm can be applied if guaranteed non-empty piecewise completability holds. Theorem 9. Let (Φ, U)be a valuation algebra, and Wa extension system. Let Ξ⊆Φbe a subset of valuations projection-closed and combination-breakable. Let φ∈Ξ,and Tbe a rooted covering join tree for a given factorization φ= φ1×· · ·×φn.If guaranteed non-empty piecewise completability holds on Ξ, then Single-Extend-To-Subtree assesses a configuration xwhich is a solution to φ. Proof. Take as loop invariant x∈cφ↓Si∈V isited λ(i),where V isited is the set of nodes of the join tree that have been visited by the loop up to some point. At the beginning of the first iteration the invariant is satisfied, since  ∈ cφ↓∅ .The update of xthat made at each interation, is possible because the conditions of Lemma 3 (including guaranteed non-emptyness) are satisfied, and hence, there is a completion that we can select, store in x,and it is guaranteed to maintain the invariant. When the last iteration finishes, we have visited all the nodes and since d(φ) = ∪i∈Vλ(i)due to Lemma 2, we have that x∈cφ. In the last three sections we have characterized under which circumstances can we apply each algorithm. In the next section we compare with the sufficient conditions provided by Pouly and Kohlas. 5.6. Alternative proofs for the PK results As we argued before, Pouly and Kohlas stated that Extend-To-GlobalProjection always assessed cφ,and we disproved by means of counterexamples. However, we have proven that projective completability is a sufficient and necessary condition for the algorithm. They did also provide sufficient conditions for the algorithms Extend-To-Subtree and Single-Extend-To-Subtree. We will see that, although the proofs relied on a disproved theorem, the results provided were correct. We do that by proving that the sufficient conditions established by them and described in section 4.1 imply our sufficient conditions. As can be seen in Table 1, CPK1 and CPK2 were proposed as sufficient condition for Extend-To-Subtree to assess some solutions and for SingleExtend-To-Subtree to assess a solution. The following lemma allows us to use theorems 7 and 9 to prove that their conditions were indeed sufficient. 23 Lemma 4. Assume that conditions CPK1 and CPK2 hold. Then, guaranteed non-empty piecewise completability holds on Φ. Proof. Take ξ1, ξ2∈Φ, with domains Xand Yrespectively, and let φ=ξ1×ξ2. To prove piecewise completability,we have to prove that CO(cφ↓X, ξ2)⊆cφ. Now by definition CO(cφ↓X, ξ2) = {(x,z)|x∈cφ↓Xand z∈WX∩Y ξ2(x↓X∩Y)}. We can apply CPK2 to get CO(cφ↓X, ξ2)⊆ {(x,z)|x∈cφ↓Xand z∈WX φ(x)}. Now, by the second condition in the definition of extension system we get CO(cφ↓X, ξ2)⊆ {(x,z)|x∈cφ↓Xand z∈WX φ(x)}=W∅ φ() = cφand piecewise completability is proven. Now we need to see that non-emptyness is guaranteed. Take Asuch that ∅ 6=A⊆cφ↓X, we have to prove that CO(A, ξ2)6=∅. Again by definition CO(A, ξ2) = {(x,z)|x∈Aand z∈WX∩Y ξ2(x↓X∩Y)}. By CPK1 we have that WX∩Y ξ2(x↓X∩Y)6=∅and so CO(A, ξ2)is guaranteed to be non-empty. Furthermore, CPK1 and CPK3 were identified as a sufficient condition for Extend-To-Subtree to assess cφ.The following lemma allows us to use theorems 7 and 9 to prove that their conditions were indeed sufficient. Lemma 5. Assume that conditions CPK1 and CPK3 hold. Then, total piecewise completability holds on Φ. Proof. Take ξ1, ξ2∈Φ, with domains Xand Yrespectively, and let φ=ξ1×ξ2. To prove piecewise total completability, we have to prove that CO(cφ↓X, ξ2) = cφ.Now by definition CO(cφ↓X, ξ2) = {(x,z)|x∈cφ↓Xand z∈WX∩Y ξ2(x↓X∩Y)}. We can apply CPK3 to get CO(cφ↓X, ξ2) = {(x,z)|x∈cφ↓Xand z∈WX φ(x)}. Now, by the second condition in the definition of extension system we get CO(cφ↓X, ξ2) = {(x,z)|x∈cφ↓Xand z∈WX φ(x)}=W∅ φ() = cφand total piecewise completability is proven. On the other hand, we point out that in both cases the sufficient conditions we require, while similar to the ones required by Pouly and Kohlas are strictly weaker than those. In particular, their conditions need to hold on any configuration x∈ΩX,whilst we only require them to hold for those x∈cφ↓X.That is, while they impose conditions on the extension of tuples which are not solutions, we restrict ourselves to solutions. Table 3 summarizes the results in this section, providing the sufficient conditions for each algorithm, whether the condition has also been proven to be also necessary and whether the condition we require is weaker than the one previously required. 6. Optimization problems in semiring induced valuation algebras Many problems in Artificial Intelligence can be expressed in terms of a particular type of valuations, namely semiring induced valuation algebras, that emerge from a mapping from tuples to the values of a commutative semiring [6, 5, 17, 30]. Particularly interesting are optimization problems, where the semiring is selective. We start by reviewing optimization problems and the result 24 Algorithm Suff. cond. Nec. cond. Weaker Solutions 3Projective completability Yes - All 5Guaranteed non-empty piecewise completability No Yes One 4Guaranteed non-empty piecewise completability Yes Yes Some 4Total piecewise completability Yes Yes All Table 3: Sufficient and necessary conditions of the generic algorithms. that an extension system can be defined when the semiring is selective. Then, by means of a counterexample, we show that the sufficient condition imposed by Pouly and Kohlas for the correctness of Extend-To-Global-Projection is not correct and propose a sufficient condition and a necessary condition for projective completability to hold on valuation algebras imposed by a selective semiring, and thus, for Extend-To-Global-Projection to work. Later, for Single-Extend-To-Subtree and Extend-To-Subtree we provide correct proofs for the sufficient conditions introduced by Pouly and Kohlas to solve the single and partial SFP. Finally we show that we can weaken the sufficient condition proposed by Pouly and Kohlas for Extend-To-Subtree to solve the complete SFP from strict monotonicity to weak cancellativity. Furthermore we show that weak cancellativity is also a necessary condition. 6.1. Optimization problems. We start by defining some basic abstract algebra structures needed to specify the problem and then we formally state the problem, which is a particular case of the SFP. Definition 10. Asemiring is a set Requipped with two binary operations + and ·, called addition and multiplication, such that (i) +is an associative and commutative operation with identity element 0, (ii) ·is an associative operation with identity element 1, (iii) multiplication left and right distributes over addition, that is a·(b+c)=(a·b) + (a·c)and (a+b)·c= (a·c) + (b·c), and (iv) multiplication by 0 annihilates R, that is a·0 = 0 ·a= 0. If ·is commutative then (R, +,·)is a commutative semiring. Theorem 10. Let hU, Ωibe a variable system, and (R, +, .)a commutative semiring.Asemiring valuation φwith domain X⊆Uis a function φ: ΩX→ R. The set of all semiring valuations with domain Xis noted ΦX, and Φ = SX⊆UΦX.Now we define d(φ) = Xif φ∈ΦX.Furthermore (φ×ψ)(x) = φ(x↓d(φ))·ψ(x↓d(ψ)).And finally φ↓Y(y) = Pz∈Ωd(φ)−Yφ(hy,zi)for Y⊆d(φ). With these operations, (Φ, U)satisfies the axioms of a valuation algebra and is called the valuation algebra induced by (R, +, .)in hU, Ωi. Proof. See Theorem PK5.2. 25 2. For X⊆Y⊆Uand φ∈ΦY,we have that φ↓X= 0Xif and only if φ= 0Y. Lemma 7. In a valuation algebra, the set NN ⊆Φof non-null elements is projection-closed and combination-breakable. Proof. From the second condition in Definition 15, we have that the set of nonnull elements is projection-closed. To prove that it is combination breakable pick any φthat is non-null and such that φ=ξ1×ξ2.Now assume that either ξ1or ξ2is null. Then by the first condition in Definition 15 we have that φis null which is a contradiction. Hence, both ξ1and ξ2must be non-null. In selective semiring induced valuation algebras, a valuation φis null if and only if φ↓∅()=0.Thus, all possible configurations in Ωd(φ)are solutions. Since Extend-To-Subtree runs the Collect algorithm as a previous step, it is easy to determine whether φis constant 0by assessing φ↓∅()=(ψ0 r)↓∅ ()and checking whether it is equal to 0.In that case we can directly return Ωd(φ). Thus, we can easily identify and solve null valuations. So, we have to concentrate on when does total piecewise completability hold on NN. Next, we define weak multiplicative cancellativity and prove that it is the sufficient and necessary condition on a semiring for Extend-To-Subtree to solve the complete optimization SFP. Definition 16. A commutative semiring Ris weakly multiplicatively cancellative if for any a, b, c ∈R, we have that a·c6= 0, and a·c=b·cimplies that a=b. Theorem 14. Let Rbe a commutative selective semiring. If Ris weakly multiplicatively cancellative then its induced valuation algebra satisfies total piecewise completability on NN. On the other hand, if the valuation algebra has one variable that can take two or more values, and total piecewise completability on NN is satisfied, then Ris weakly multiplicatively cancellative. Proof. We start proving that, if the semiring is weakly multiplicatively cancellative, we have total piecewise completability on NN. Take a valuation φ=ξ1×ξ2 where ξ1, ξ2∈Φ, with domains Xand Yrespectively. We have to prove that CO(cφ↓X, ξ2) = cφ. By definition of set of completions, we have that CO(cφ↓X, ξ2) = {(x,z)|x∈cφ↓Xand z∈WX∩Y ξ2(x↓X∩Y)}. Now, from the definition of cφ,we have that cφ=W∅ φ() = {(x,z)|x∈cφ↓Xand z∈WX ξ1×ξ2(x)}. So, total piecewise completability is satisfied if, and only if, for each x∈cφ↓X, we have that WX∩Y ξ2(x↓X∩Y) = WX ξ1×ξ2(x). 32 In Theorem 13, we proved that WX∩Y ξ2(x↓X∩Y)⊆WX ξ1×ξ2(x).Thus, it remains to prove that WX ξ1×ξ2(x)⊆WX∩Y ξ2(x↓X∩Y). Now take z∈WX ξ1×ξ2(x).From the definition we have that (ξ1×ξ2)(x,z) = (ξ1×ξ2)↓X(x).From here, (ξ1×ξ2)(x,z) = (ξ1×ξ↓X∩Y 2)(x) and by definition of combination ξ1(x)·ξ2((x↓X∩Y,z)) = ξ1(x)·ξ↓X∩Y 2(x). We have that ξ1(x)·ξ↓X∩Y 2(x) = φ↓X(x) = φ↓∅()6= 0,where the second equality follows because x∈cφ↓X,and the third one since φ∈NN, and hence φ↓∅()6= 0.So we can apply weak cancellation to ξ1(x)getting ξ2((x↓X∩Y,z)) = ξ↓X∩Y 2(x↓X∩Y). But this is exactly the condition that zhas to satisfy in order to be in WX∩Y ξ2(x↓X∩Y).We have proven that WX ξ1×ξ2(x)⊆WX∩Y ξ2(x↓X∩Y)and in Theorem 13, we proved that WX∩Y ξ2(x↓X∩Y)⊆WX ξ1×ξ2(x).Thus, WX∩Y ξ2(x↓X∩Y) = WX ξ1×ξ2(x). The second part of the proof assumes total piecewise completability on NN and concludes that the semiring must be weakly multiplicatively cancellative. To prove it, we assume that it is not and will reach a contradiction. Let a, b, c ∈R, such that a·c6= 0, a ·c=b·cand a6=b. Now, we build a valuation which has as domain a single variable xwith at least two values, namely x0and x1. φ(x)=(ξ1×ξ2)(x) with ξ1() = c, and ξ2(x) =      aif x=x0, bif x=x1, 0otherwise. Note that φis non-null and that the set of solutions of φis {x0, x1}.Now, if a > b, then W∅ ξ2() = {x0},and the only solution found by piecewise completing will be {x0}.On the other hand, if b > a, then then W∅ ξ2() = {x1},and the only solution found by piecewise completing will be {x1}.Thus, in both cases we get to a contradiction. Table 4 summarizes the results in this section, providing the sufficient and necessary conditions for each algorithm. We have proven a sufficient condition to Extend-To-Global-Projection, which correctly deals with counterexample 3. For Extend-To-Subtree to solve the complete optimization SFP, 33 Algorithm Problem Semiring suff. cond. Semiring nec. cond. 3Complete optimization SFP Square multiplicatively cancellative on image Square ordered 5Single optimization SFP None None 4Partial optimization SFP None None 4Complete optimization SFP Weakly multiplicatively cancellative Weakly multiplicatively cancellative Table 4: Sufficient and necessary conditions on optimization problems (semirings considered are always commutative and selective). Pouly and Kohlas required strict monotonicity which, for selective semirings, is equivalent to multiplicative cancellativity (see Proposition 3). We have proven that weakly multiplicative cancellativity suffices. Furthermore, where possible, we have provided also necessary conditions. 7. Conclusions The theory for the generic construction of solutions in valuation based systems [22, 23] studies three widely used dynamic programming algorithms from the most general perspective and provides necessary conditions for those algorithms to be correct. We have presented counterexamples to the results presented there and we have shown that the counterexamples have a deep impact in the theory. This has opened the way for identifying two properties of extension systems: projective completability and piecewise completability. We have proven that such properties constitute sufficient and necessary conditions for those generic algorithms to be correct, allowing for a sharper characterization of when each algorithmic scheme can be applied. To the best of our knowledge, up to know no necessary conditions for these generic algorithms had been presented in the literature. A particularly interesting case where these algorithms can be applied is valuation algebras induced by a commutative selective semiring, where they constitute the base of well known optimization algorithms. For that case, we have also corrected a result in [22, 23]. Furthermore, we have been able to translate the sufficient and necessary conditions for the algorithms into conditions for the semiring, identifying three new semiring properties: square multiplicatively cancellative on image, square ordered and weakly multiplicatively cancellative. Although we have started scratching the relationships between these semiring properties, a deeper study of their interactions remains as future work. As a result, our corrected theory provides the more general description of these generic algorithms and the sharpest characterization to date of their necessary and sufficient conditions. 34 Acknowledgements The authors would like to thank Professor Jürg Kohlas for his many valuable comments, suggestions and discussions along the craft of this paper. This work has been supported by projects COR (TIN2012-38876-C02-01), GEAR (CSIC - 201350E112) and by the Generalitat of Catalunya grant 2009-SGR-1434. A. Properties of rooted covering join trees We prove some poperties of rooted covering join trees which are needed to ease the proofs of the results presented in the paper. In any rooted join tree, for each node i∈V, we define λde(i)as the set of variables that appear in the scope of the descendants of i, namely λde(i) = Sj∈de(i)λ(j). Furthermore we define λnde(i)as the set of variables that appear in the scope of the non-descendants of i, namely λnde(i) = Sj∈nde(i)λ(j). Lemma 8. For any node iof V si=λ(i)∩λnde(i)(A.1) [ j∈ch(i) sj=λ(i)∩λde(i)(A.2) λnde(i)∩λde(i)⊆λ(i)∩λde(i)(A.3) Proof. We start proving equation A.1. If iis the root, then si=∅and the equation is trivially satisfied. Assume that iis not the root. By definition of λnde(i), we have that λ(i)∩λnde(i) = λ(i)∩Sj∈nde(i)λ(j) = Sj∈nde(i)(λ(i)∩ λ(j)) = si∪Sj∈nde(i)−{pi}(λ(i)∩λ(j)).For any j∈nde(i)− {pi},we have that pilies in the path between jand i, and by the running intersection property, λ(i)∩λ(j)⊆λ(pi). Since λ(i)∩λ(j)⊆λ(i),we have that λ(i)∩λ(j)⊆ λ(i)∩λ(pi) = si.Thus, Sj∈nde(i)−{pi}λ(i)∩λ(j)⊆si,and λ(i)∩λnde(i) = si. Next, we will prove equation A.2 λ(i)∩λde(i) = λ(i)∩[ j∈de(i) λ(j) = λ(i)∩[ j∈ch(i) [λ(j)∪[ k∈de(j) λ(k)] =[ j∈ch(i) [(λ(i)∩λ(j)) ∪[ k∈de(j) (λ(i)∩λ(k))]. Now, by the running intersection property, λ(i)∩λ(k)⊆λ(i)∩λ(j),so we can remove the union Sk∈de(j)(λ(i)∩λ(k)) leaving λ(i)∩λde(i) = [ j∈ch(i) [λ(i)∩λ(j)] = [ j∈ch(i) sj. Finally, we will conclude by proving equation A.3. Applying the definitions we have that λnde(i)∩λde(i) = Sj∈nde(i)λ(j)∩Sk∈de(i)λ(k)= 35 Algorithm 6 MinimalLambdas algorithm 1: for all nodes iof Tdo 2: α(i) := Sj∈a−1(i)d(φj) 3: β(i) := α(i) 4: γ(i) := ∅ 5: end for 6: for all nodes iof Texcept the root in an upward order do 7: α(pi) := α(pi)∪α(i) 8: β(pi) := β(pi)∪(γ(pi)∩α(i)) 9: γ(pi) := γ(i)∪α(i) 10: end for 11: λ(r) := β(r) 12: for all nodes iof Texcept the root in an downward order do 13: λ(i) := β(i)∪(λ(pi)∩α(i)) 14: end for 15: return λ; Sj∈nde(i)Sk∈de(i)λ(j)∩λ(k).But now node ilies in the path between any node jwhich is non-descedant of iand any other node kwhich is descendant of i. Thus, by the running intersection property we have that λ(j)∩λ(k)⊆ λ(i),and that Sj∈nde(i)Sk∈de(i)λ(j)∩λ(k)⊆λ(i).From here we have that λnde(i)∩λde(i)⊆λ(i)∩λde(i). B. Minimally labeled covering join trees In the paper we make the assumption that covering join trees are minimally labeled (see Assumption 1). In this appendix we start by checking that, for a fixed tree, there is no covering join tree whose labels are smaller that those of a minimally labeled join tree. Afterwards, we prove that it is easy to build a minimally labeled covering join tree provided a tree and a valuation assignment function. Finally we prove some properties of minimally labeled covering join trees which are used in the proofs in the paper. We start by proving that there can be no labelling smaller than that of a minimally labeled covering join tree. Lemma 9. Let (V, E)be a tree. Given a valuation φ=φ1× · · · × φn,there is no covering join tree T= (V, E, λ, U), valuation assignment a,i∈V, and k∈ne(i),such that λ(i)+d(ψi)∪Sj∈ne(i)\{k}sij. Proof. The proof is immediate since sij =λ(i)∩λ(j)⊆λ(i)and d(ψi)⊆λ(i) is required for ato be a valuation assignment. Now, Algorithm 6 provides a procedure to assess a minimally labeled covering join tree provided a covering join tree and a valuation assignment a. Lemma 10. MinimalLambdas asseses a minimally labeled covering join tree. Furthermore MinimalLambdas only requires time and space O(|V||U|),where Vis the set of nodes of the join tree and Uis the set of variables of the problem. 36 Proof. We will start proving that MinimalLambdas asseses a covering join tree. Let φ=φ1, . . . , φnbe a valuation and let T= (V, E, λ, U)be a tree where the MinimalLambdas algorithm has been run. After the second loop we have α(i) = d(ψi)∪Sj∈de(i)d(ψj)and β(i) = d(ψi)∪    [ j,k∈ch(i) j6=k α(j)∩α(k)     .(B.1) Notice that β(i)⊆α(i)and as a consequence λ(i) = β(i)∪(λ(pi)∩α(i)) ⊆ α(i)∪(λ(pi)∩α(i)) ⊆α(i).Also notice that for any i∈de(j),α(i)⊆α(j). After the third loop we get λ(i) = β(i)∪(λ(pi)∩α(i)).Thus, λ(pi)∩α(i)⊆λ(i). Next we will prove that the runing intersection property is satisfied. Let n1, n2, . . . , nmbe the unique path between two given nodes n1, nm∈V. We want to see that λ(n1)∩λ(nm)⊆λ(ni),for 1<i<m. Notice that if m≤2 it is trivially true. Therefore we will suppose m≥3. As long as Tis a tree, the previous path can be seen as the composition of two different paths, one ascending path which grows up from n1up to niwith 1≤i≤m, and one descending path from nito nm. That is nj+1 =pnjfor 1≤j≤i−1and nj+1 ∈ch(nj)for i≤j≤m−1.Notice that if n16=nmat most one of these subpaths may be empty. Hence there are three possible configurations for the paths either the descending path is empty, or the ascending path is empty or no subpath is empty. Equivalently, either i=mor i= 1 or 1im. 1. Assume that the descending path is empty, so i=m. We have that λ(n1)∩λ(nm)⊆λ(n1)⊆α(n1)⊆α(nm−1)and λ(n1)∩λ(nm)⊆λ(nm) = λ(pnm−1).In conclusion we obtain λ(n1)∩λ(nm)⊆α(nm−1)∩λ(pnm−1)⊆ λ(nm−1), and we have verificed that nm−1fulfills the condition. Now since, by induction we have that λ(n1)∩λ(nm)⊆λ(nj),for 1< j < m. 2. In case the ascending path is empty we can consider the path from nmto n1and use the previous argument, since nm, nm−1, . . . , n1is an ascending path. 3. Finally, if no subpath is empty it holds that 1im. In this case, we have that λ(n1)⊆α(n1)⊆α(ni−1)and λ(nm)⊆α(nm)⊆α(ni+1). Since ni−1, ni+1 ∈ch(ni)we obtain: λ(n1)∩λ(nm)⊆α(ni−1)∩α(ni+1)⊆ [ j,k∈ch(i) j6=k α(j)∩α(k)⊆β(i)⊆λ(i),and thus the condition is fulfilled for i. As long as n1, . . . , niis an ascending path and ni, . . . , nmis a descending path, we can use the previous cases to check that λ(n1)∩λ(ni)⊆λ(nj) for 1≤j≤m, which concludes the proof since λ(n1)∩λ(nm) = λ(n1)∩ λ(nm)∩λ(ni)⊆λ(n1)∩λ(ni)⊆λ(nj). We have just shown that Tis a join tree, but as long as for all ψ(i)it is satisfied d(ψi)⊆λ(i)we also have that Tis actually a covering join tree. Next, we will prove that Tis minimally labeled. By lemma 9 we already know that λ(i)⊇d(ψi)∪Sj∈ne(i)\{k}sij for all i∈V. We will prove by contradiction that λ(i) = d(ψi)∪Sj∈ne(i)\{k}sij.Assume that for some i∈Vthere 37 is a variable x∈λ(i)and a k0∈ne(i)such that x /∈d(ψi)∪Sj∈ne(i)\{k0}sij. Since λ(i) = β(i)∪(λ(pi)∩α(i)), we have that x∈β(i)or x∈λ(pi)∩α(i). 1. If x∈β(i),since by assumption x /∈d(ψi),we can conclude from equation B.1 that x∈Sj,k∈ch(i) j6=k α(j)∩α(k). Nonetheless, if there are j, k ∈ch(i) such that x∈λ(j)and x∈λ(k), then by the running intersection property x∈λ(i)and as a consequence x∈si,j and x∈sik.For any possible value of k0,either sij or sik will be part of Sj∈ne(i)\{k0}sij., and thus, we have a contradiction. 2. If x∈λ(pi)∩α(i). We have x∈α(i) = d(ψi)∪Sj∈de(i)d(ψj)and x∈λ(pi). Since by assumption x /∈d(ψi),then x∈Sj∈de(i)d(ψj). Nevertheless, x∈Sj∈de(i)d(ψj)implies x∈Sj∈de(i)λ(j), and by the running intersection property, there must exist at least one j∈ch(i)such that x∈λ(j), in particular x∈si,j , which also contradicts our hypothesis since x∈λ(pi)implies x∈si,pi. B.1. Basic properties of minimally labeled covering join trees In the following, let T= (V, E, λ, U)be a minimally labeled covering join tree. Removing any edge {i, j} on the T, breaks it into two different trees: T−j i, the one containing iand T−i j,the one containing j. Lemma 11. For any edge {i, j}of T, [ k∈T −j i λ(k) = d(Y k∈T −j i ψk)(B.2) Proof. We can place iat the root and use induction on the height of the tree. If iis a leaf, then it is trivially true, since both sides are d(ψi). Let ibe a node with height nand assume it is true whenever the height is smaller than n. Each node in Tilies in a subtree rooted at one of the children of i, so Sk∈T −j iλ(k) = λ(i)∪Sj0∈ne(i)−{j}Sk0∈T −i j0λ(k0)Now applying the minimally labeled assumption to λ(i)with k=jwe get λ(i) = d(ψi)∪ Sj0∈ne(i)−{j}sij0.Thus,Sk∈T −j iλ(k) = d(ψi)∪Sj0∈ne(i)−{j}sij0∪Sk0∈T −i j0λ(k0). By definition each separator sij0⊆λ(j0),and hence sij0⊆Sk0∈T −i j0λ(k0),so we can remove the sij0from the previous expression, getting Sk∈T −j iλ(k) = d(ψi)∪Sj0∈ne(i)−{j}Sk0∈T −i j0λ(k0).Now we can apply the induction hypothesis on each children j, getting Sk0∈T −i j0λ(k0) = d(Qk0∈T −i j0ψk0)and the proof is finished. Corollary 2. Let φ=φ1×· · ·×φnbe a valuation and let T= (V, E, λ, U)a minimally labeled covering join tree for this factorization. Then, d(φ) = Si∈Vλ(i). 38 Proof. By induction on the height of the tree, parallel to the one of the previous Lemma. Lemma 12. For any node iof V, λde(i) = d(Y j∈de(i) ψj)(B.3) Proof. Every descendant of ilies on the subtree of one of its childs. Thus, λde(i) = Sj∈ch(i)Sk∈T −i jλ(k)and by direct application of Lemma 11 we get λde(i) = Sj∈ch(i)d(Qk∈T −i jψk)) = d(Qj∈ch(i)Qk∈T −i jψk)) = d(Qj∈de(i)ψj). Lemma 13. For any node iof V, λnde(i) = d(Y j∈nde(i) ψj)(B.4) Proof. Directly applying Lemma 11 to the link {pi, j},since the set of nodes in T−i piis exactly nde(i). C. Piecewise and projective extensibility In this section we concentrate on proving proposition 1. Let us start by recalling it. Proposition 1. There are valuation algebras and extension system satisfying: 1. neither projective nor piecewise completability, 2. projective completability but not piecewise completability, 3. piecewise completability but not projective completability, 4. both piecewise and projective completability. We will provide an example of valuation algebras and extension system in each of the four categories. A simple example of valuation algebra and extension system such that none of the completabilities are satisfied is the one provided in counterexample 2. As for the fourth category, any valuation algebra induced by the semiring (R,max,·) satisfies both piecewise and projective extensibility. The valuation algebra presented in counterexample 3 satisfies piecewise completability but does not satisfy projective completability. Next, we provide an example of valuation algebra satisfying projective completability but not piecewise completability. Let U={x, y}be a set with two variables. Let Dx=Dy={0,1}and Ω the set of all tuples. We have that hU, Ωiare a variable system. Consider the 39 valuation algebra induced by the semiring (R,max,+). Let φ1: ΩX→R, and φ2: ΩY→R,be two valuations defined as φ1((x7→ 0)) = 2 φ2((y7→ 0)) = 2 φ1((x7→ 1)) = 1 φ2((y7→ 1)) = 1 Taking Ψ = {φa 1×φb 2×(φ↓∅ 1)c×(φ↓∅ 2)d}, it is easy to prove that (Ψ, U)fulfils the axioms of a valuation algebra. Next, we have to define the extension sets in (Ψ, U0). We will build a new extension system Win the following way: •For φ1we define its extensible solutions W∅ φ1() = cφ1={(x7→ 0),(x7→ 1)} •For φ2we define W∅ φ1() = cφ2={(y7→ 0),(y7→ 1)}. •For any other valuation ψ∈Ψ, with d(ψ) = Xwe define W∅ ψ() = cψ= {(x7→ 0)}. •For any other valuation ψ∈Ψ, with d(ψ) = Ywe define W∅ ψ() = cψ= {(y7→ 0)}. •For any other valuation ψ∈Ψ, with d(ψ) = X∪Ywe define W∅ ψ() = cψ={((x, y)7→ (0,0))}. This definition guarantees that Wis an extension system on (Ψ, U). We will now see that the valuation algebra (Ψ, U)with extension system W satisfies projectitve extensibility but does not satisfy piecewise extensibility. For any valuation with domain Xit is immediate to prove that it is projective extensible since there is no domain ∅(D(X. Same holds for any valuation with domain Y. For any valuation ψ, such that d(ψ) = X∪Ywe have cψ={((x, y)7→ (0,0))}.Additionaly it holds cψ↓X={(x7→ 0)}and cψ↓Y={(y7→ 0)}. In particular we have thatψis projective extenible. We have just shown that all the valuations in (Ψ, U)are projective extensible. Hence we only have to find a valuation which is not piecewise extensible. Let φ=φ1×φ2. Since cφ↓X={(x7→ 0)}and cφ2={(y7→ 0),(y7→ 1)}we have CO(cφ↓X, φ2) = {(x, y)→(0,0),(x, y)→(0,1)} 6⊆ ¯cφ={((x, y)7→ (0,0))} Hence φis not piecewise extensible. In particular, all the valuations in (Ψ, U)with extension system Ware projective extensible but not all of them are projective extensible. Indeed, it can be seen that the only piecewise extensible valuations are φ1and φ2. 40 D. Some selective semirings properties Definition 17. Let (R, +,·)be a semiring. If for each a∈R, a +a=a, the semiring is idempotent. Corollary 3. Let (R, +,·)be a commutative semiring. Then (R, +,·)is selective if, and only if, (R, +,·)is totally ordered and idempotent. Proof. Assume now that (R, +,·)is idempotent and totally ordered and take a, b ∈R. Without loss of generality we can assume a≤b, i.e. there is c∈R such that a+c=b. Therefore a+b=a+ (a+c) = (a+a) + c=a+c=b. This proves the if part. To prove the only if part, note that any selective semiring is idempotent. Moreover, we have already seen that as a consequence of Proposition 3.4.7 in [13], any selective semiring is totally ordered. Definition 18. A selective semiring is strict monotonic if whenever c6= 0, a < b implies that a·c<b·c. A selective semiring is multiplicatively cancellative if whenever c6= 0, a ·c= b·cif and only if a=b. Proposition 3. Let (R, +,·)be a selective semiring. Then (R, +,·)is strict monotonic if and only if (R, +,·)is multiplicatively cancellative. Proof. Assume that (R, +,·)is multiplicatively cancellative. Given a, b, c ∈R with c6= 0 we want to see that a<b⇒a·c<b·c. Since a<bwe have that b=a+b. By multiplying by cat both sides of the equality we get b·c= (a+b)·c=a·c+b·c. Hence, there exist d=b·c∈Rsuch that a·c+d=b·c. By definition of the canonical order induced by +we have a·c≤b·c. Since we have multiplicative cancellativity a·c=b·cimplies a=b which is a contractiction. Hence a·c6=b·c. In particular a·c<b·c. Assume that (R, +,·)is strict monotonic. Given a, b, c ∈Rwith a·c6= 0we want to see that a=b⇔a·c=b·c. Notice that a=balways implies a·c=b·c,so we only have to prove the inverse implication. Assume a·c=b·c holds. Since the semiring is totally ordered we have either a≤bor b≤a. Since b·c=a·c6= 0 we can assume without loss of generality that a≤b. If ab then by strict monotonicity we have a·cb·cwhich is a contradiction. Hence a=b. 41