Maxime Chaveroche

Véronique Franck Davoine

Véronique Cherfaoui

Efficient Möbius Transformations and their applications to Dempster-Shafer Theory: Clarification and implementation ⋆

Keywords: Möbius Transform, Zeta Transform, Efficiency, distributive lattice, meet-closed subset, join-closed subset, Fast Möbius Transform, FMT, Dempster-Shafer Theory, DST, belief functions, efficiency, information-based, complexity reduction

published or not. The documents may come

Efficient Möbius Transformations and their applications

to Dempster-Shafer Theory: Clarification and implementation ⋆

Introduction

Dempster-Shafer Theory (DST) [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] is an elegant formalism that generalizes Bayesian probability theory. It is more expressive by giving the possibility for a source to represent its belief in the state of a variable not only by assigning credit directly to a possible state (strong evidence) but also by assigning credit to any subset (weaker evidence) of the set Ω of all possible states. This assignment of credit is called a mass function and provides meta-information to quantify the level of uncertainty about one's believes considering the way one established them, which is critical for decision making.

Nevertheless, this information comes with a cost: considering 2 |Ω| potential values instead of only |Ω| can lead to computationally and spatially expensive algorithms. They can become difficult to use for more than a dozen possible states (e.g. 20 states in Ω generate more than a million subsets), although we may need to consider large frames of discernment (e.g. for classification or identification tasks). Moreover, these algorithms not being tractable anymore beyond a few dozen states means their performances greatly degrade before that, which further limits their application to real-time applications. To tackle this issue, a lot of work has been done to reduce the complexity of transformations used to combine belief sources with Dempster's rule [START_REF] Dempster | A Generalization of Bayesian Inference[END_REF]. We distinguish between two approaches that we call powerset-based and evidence-based.

The powerset-based approach concerns all algorithms based on the structure of the powerset 2 Ω of the frame of discernment Ω. They have a complexity dependent on |Ω|. Early works [START_REF] Barnett | Computational Methods for a Mathematical Theory of Evidence[END_REF][START_REF] Gordon | A method for managing evidential reasoning in a hierarchical hypothesis space[END_REF][START_REF] Shenoy | Propagating Belief Functions with Local Computations[END_REF][START_REF] Shafer | Implementing Dempster's rule for hierarchical evidence[END_REF] proposed optimizations by restricting the structure of evidence to only singletons and their negation, which greatly restrains the expressiveness of DST. Later, a family of optimal algorithms working in the general case, i.e. the ones based on the Fast Möbius Transform (FMT) [START_REF] Kennes | Computational aspects of the Mobius transformation of graphs[END_REF], was discovered. Their complexity is O(|Ω|.2 |Ω| ) in time and O(2 |Ω| ) in space. It has become the de facto standard for the computation of every transformation in DST. Consequently, efforts were made to reduce the size of Ω to benefit from the optimal algorithms of the FMT. More specifically, [START_REF] Wilson | Algorithms for Dempster-Shafer Theory[END_REF] refers to the process of conditioning by the combined core (intersection of the unions of all focal sets of each belief source) and lossless coarsening (merging of elements of Ω which always appear together in focal sets). Also, Monte Carlo methods [START_REF] Wilson | Algorithms for Dempster-Shafer Theory[END_REF] have been proposed but depend on a number of trials that must be large and grows with |Ω|, in addition to not being exact.

The evidence-based approach concerns all algorithms that aim to reduce the computations to the only subsets that contain information (evidence), called focal sets, which are usually far less numerous than 2 |Ω| . This approach, also refered to as the obvious one, implicitly originates from the seminal work of Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] and is often more efficient than the powerset-based one since it only depends on information contained in sources in a quadratic way. Doing so, it allows for the exploitation of the full potential of DST by enabling us to choose any frame of discernment, without concern about its size. Moreover, the evidence-based approach benefits directly from the use of approximation methods, some of which are very efficient [START_REF] Sarabi-Jamab | Information-Based Evaluation of Approximation Methods in Dempster-Shafer Theory[END_REF]. Therefore, this approach seems superior to the FMT in most use cases, above all when |Ω| is large, where an algorithm with exponential complexity is just intractable.

It is also possible to easily find evidence-based algorithms computing all DST transformation, except for the conjunctive and disjunctive decompositions for which we recently proposed a method [START_REF] Chaveroche | Calcul exact de faible complexité des décompositions conjonctive et disjonctive pour la fusion d'information[END_REF][START_REF]Efficient exact computation of the conjunctive and disjunctive decompositions of D-S Theory for information fusion: Translation and extension[END_REF]. However, since these algorithms rely only on the information contained in sources, they do not exploit the structure of the powerset to reduce the complexity, leading to situations in which the FMT can be more efficient if almost every subset contains information, i.e. if the number of focal sets tends towards 2 |Ω| [START_REF] Wilson | Algorithms for Dempster-Shafer Theory[END_REF], all the most when no approximation method is employed.

In this paper, we fuse these two approaches into one, proposing new sequences of graphs, in the same fashion as the FMT, that are always more efficient than the FMT and can in addition benefit from evidence-based optimizations. We call them the Efficient Möbius Transformations (EMT). More generally, our approach applies to any function defined on a finite distributive lattice.

Outside the scope of DST, [START_REF] Björklund | Trimmed Moebius inversion and graphs of bounded degree[END_REF] is related to our approach in the sense that we both try to remove redundancy in the computation of the zeta and Möbius transforms on the subset lattice 2 Ω . However, they only consider the redundancy of computing the image of a subset that is known to be null beforehand. To do so, they only visit sets that are accessible from the focal sets of lowest rank by successive unions with each element of Ω. Here, we demonstrate that it is possible to avoid far more computations by reducing them to specific sets so that each image is only computed once. These sets are the focal points described in [START_REF] Chaveroche | Calcul exact de faible complexité des décompositions conjonctive et disjonctive pour la fusion d'information[END_REF][START_REF]Efficient exact computation of the conjunctive and disjunctive decompositions of D-S Theory for information fusion: Translation and extension[END_REF]. The study of their properties will be carried out in depth in an upcoming article [START_REF] Chaveroche | Focal points and their implications for möbius transforms and dempster-shafer theory[END_REF]. Besides, our method is more general since it applies to any finite distributive lattice.

Furthermore, an important result of our work resides in the optimal computation of the zeta and Möbius transforms in any intersection-closed family F of sets from 2 Ω , i.e. with a complexity O(|Ω|.|F |). Indeed, in the work of [START_REF] Björklund | Fast zeta transforms for lattices with few irreducibles[END_REF] on the optimal computation of these transforms in any finite lattice L, they embedded L into the Boolean lattice 2 Ω , obtaining an intersection-closed family F as its equivalent, and found a meta-procedure building a circuit of size O(|Ω|.|F |) computing the zeta and Möbius transforms. However, they did not managed to build this circuit in less than O(|Ω|.2 |Ω| ). Given F , our Theorem 3.2.2 in this paper directly computes this circuit with a complexity that can be as low as O(|Ω|.|F |) in some instances, while being much simpler.

This paper is organized as follows: Section 2 will present the elements on which our method is built. Section 3 will present our EMT. Section 4 will discuss their complexity and their usage both in general and in the case of DST. Finally, we will conclude this article with section 5.

Background of our method

Let (P, ≤) be a finite1 set partially ordered by ≤.

Zeta transform

The zeta transform g : P → R of a function f : P → R is defined as follows:

∀y ∈ P, g(y) = x≤y f (x) (1)
This can be extended to the multiplication as the multiplicative zeta transform:

∀y ∈ P, g(y) = Example 2.1.3. In DST, the commonality function q is defined as the zeta transform of the mass function m in (2 Ω , ⊇), i.e.:

∀B ∈ 2 Ω , q(B) = A⊇B m(A)
Example 2.1.4. In DST, the commonality function q is also the inverse of the multiplicative zeta transform of the conjunctive weight function w in (2 Ω , ⊇), i.e.:

∀B ∈ 2 Ω , q(B) = A⊇B w(A) -1

Möbius transform

The Möbius transform of g is f . It is defined as follows:

∀y ∈ P, f (y) = x≤y g(x).µ P,≤ (x, y)

where µ P,≤ is the Möbius function of (P, ≤) (See [START_REF] Rota | On the foundations of combinatorial theory I. Theory of Möbius functions[END_REF]). There is also a multiplicative version with the same properties that can be seen as the exponential of the Möbius transform of log • g:

∀y ∈ P, f (y) = x≤y g(x) µ P,≤ (x,y)
Example 2.2.1. In DST, the mass function m is the Möbius transform of the implicability function b in (2 Ω , ⊆), i.e.:

∀B ∈ 2 Ω , m(B) = A⊆B b(A).µ 2 Ω ,⊆ (A, B)
where for any A, B ∈ 2 Ω , the Möbius function evaluates to µ 2 Ω ,⊆ (A, B) = (-1) |B|-|A| , as recalled in [START_REF] Kennes | Computational aspects of the Mobius transformation of graphs[END_REF].

Example 2.2.2. In DST, the disjunctive weight function v is the inverse of the multiplicative Möbius transform of the implicability function b in (2 Ω , ⊆), i.e.:

∀B ∈ 2 Ω , v(B) = A⊆B b(A) -µ 2 Ω ,⊆ (A,B)
Example 2.2.3. In DST, the mass function m is the Möbius transform of the commonality function q in (2 Ω , ⊇), i.e.:

∀B ∈ 2 Ω , m(B) = A⊇B q(A).µ 2 Ω ,⊇ (A, B)
where for any A, B ∈ 2 Ω , the Möbius function also evaluates to

µ 2 Ω ,⊇ (A, B) = (-1) |B|-|A| .
Example 2.2.4. In DST, the conjunctive weight function w is the inverse of the multiplicative Möbius transform of the commonality function q in (2 Ω , ⊆), i.e.:

∀B ∈ 2 Ω , w(B) = A⊇B q(A) -µ 2 Ω ,⊇ (A,B)

Sequence of graphs and computation of the zeta transform

To yield g(y) for some y ∈ P , we must sum all values f (x) such that x ≤ y. Our objective is to do it in the minimum number of operations, i.e. to minimize the number of terms to sum. If we only compute g(y) alone, we have to pick every element in {x ∈ P / x ≤ y} and sum their associated values through f . However, if we compute g(y) for all elements y ∈ P at once, we can organize and mix these computations so that partial sums are reused for more than one value through g. Indeed, for any element y ∈ P , if there is an element z ∈ P such that y ≤ z, we have g(z) = g(y) + x≤z x ≤y f (x). So, we want to recursively build partial sums so that we can get the full sum on each g(y) by only summing the values on some elements from {x ∈ P / x ≤ y}. In other words, we would like to define an ordered sequence of transformations computing g from f .

Let us adopt the formalism of graph theory. Let G ≤ be a directed acyclic graph in which the set of its nodes matches P and each arrow is directed by ≤. Let E ≤ be the set of its arrows. We have E ≤ = {(x, y) ∈ P 2 / x ≤ y} and G ≤ = (P, E ≤ ). Thus, computing g(y) alone is equivalent to visiting the node y from all nodes x of G ≤ such that there is an arrow (x, y) ∈ E ≤ . Each "visit" to node y from a node x corresponds to the computation of the operation f (x) + •, where • represents the current state of the sum associated with y. Thus, G ≤ , combined with the binary operator f (•) + •, describes the transformation of 0 into g. More concisely, we will equivalently initialize our algorithm with values through f instead of 0 and exploit the combination of G < and +. We will say that the transformation (G < , f, +) computes the zeta transform of f in (P, ≤). In the end, we want to minimize the number of "visits" to be made to all y, i.e. we want to minimize the total number of arrows to follow to compute every g(y). Therefore, the question is: Is there an ordered sequence of graphs that can compute g from f with less arrows in total than (G < , f, +) ? Let I P be the set containing all identity arrows of G ≤ , i.e. I P = { (x, y) ∈ P 2 / x = y}. Consider that all elements y ∈ P are initialized with f (y). We are interested in finding a sequence of graphs that is equivalent to the arrows of G < . Let (H i ) i∈ 1,n be a sequence of n directed acyclic graphs H i = (P, E i ). We will note ((H i ) i∈ 1,n , f, +) the computation that transforms f into h 1 through the arrows of E 1 , then transforms h 1 into h 2 through the arrows of E 2 , and so on until the transformation of h n-1 into h n through the arrows of E n . We ignore all identity arrows in these computations. So, this sequence of graphs requires us to consider

|E 1 | + |E 2 | + • • • + |E n | arrows, but transforms f into h n in |E 1 \I P | + |E 2 \I P | + • • • + |E n \I P | operations. Proposition 2.3.1. Let Ω = {ω 1 , ω 2 , . . . , ω n }. One particular sequence of interest is (H i ) i∈ 1,n , where H i = (2 Ω , E i ) and: E i = {(X, Y ) ∈ 2 Ω × 2 Ω / Y = X ∪ {ω i }}.
This sequence computes the same zeta transformations as

G ⊂ = (2 Ω , E ⊂ ), where E ⊂ = {(X, Y ) ∈ 2 Ω × 2 Ω / X ⊂ Y }.
Example 2.3.1. Let us say that Ω = {a, b, c}. Crossing ignored arrows (i.e. identity arrows), we have: This sequence computes the same zeta transformations as G⊂ = (2 Ω , E⊂), where

• E 1 = {(X, Y ) ∈ 2 Ω × 2 Ω / Y = X ∪ {a}} = { (∅, {a}), ✘ ✘ ✘ ✘ ✘ ❳ ❳ ❳ ❳ ❳ ({a}, {a}), ({b}, {a, b}), ✭ ✭ ✭ ✭ ✭ ✭ ✭ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ({a, b}, {a, b}), ({c}, {a, c}), ✭ ✭ ✭ ✭ ✭ ✭ ✭ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ({a, c}), {a, c}), ({b, c}, Ω), ✘ ✘ ✘ ❳ ❳ ❳ (Ω, Ω) } ∅ {a} {b} {a, b} {c} {a, c} {b, c} Ω • • • • • • • • 1 : Y = X ∪ {a} • • • • • • • • 2 : Y = X ∪ {b} • • • • • • • • 3 : Y = X ∪ {c} • • • • • • • •
E⊂ = {(X, Y ) ∈ 2 Ω × 2 Ω / X ⊂ Y }.
A dot represents the node of its column. Its row i corresponds to both the tail of a potential arrow in Hi and the head of a potential arrow in Hi-1. The last row corresponds to the heads of all potential arrows that could be in H3. The arrows represents the actual arrows in each graph Hi.

Identity arrows are ignored in computations and not displayed here for the sake of clarity. If they were, there would be vertical arrows in every column, linking each dot in row i to the next dot of same node in row i + 1. This representation is derived from the one used in [START_REF] Kennes | Computational aspects of the Mobius transformation of graphs[END_REF]. 1 illustrates this sequence. Check that, after execution of ((H i ) i∈ 1,n , f, +), each element y of 2 Ω is associated with the sum x⊆y f (x). For instance, let us take a look at Ω. Initially, each element of 2 Ω is associated with its value through f . Then, at step 1, we can see that the value on Ω is summed with f ({b, c}). At step 2, it is summed with h 1 ({a, c}), which is equal to f ({c})+f ({a, c}), following step 1. Finally, at step 3, it is summed with h 2 ({a, b}), which is equal to h 1 ({a})+h 1 ({a, b}) following step 2, which is itself equal to f (∅)+f ({a})+f ({b})+f ({a, b}), following step 1. Gathering all these terms, we get that

• E 2 = {(X, Y ) ∈ 2 Ω × 2 Ω / Y = X ∪ {b}} = { (∅, {b}), ({a}, {a, b}), ✘ ✘ ✘ ✘ ✘ ❳ ❳ ❳ ❳ ❳ ({b}, {b}), ✭ ✭ ✭ ✭ ✭ ✭ ✭ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ({a, b}, {a, b}), ({c}, {b, c}), ({a, c}), Ω), ✭ ✭ ✭ ✭ ✭ ✭ ✭ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ({b, c}, {b, c}), ✘ ✘ ✘ ❳ ❳ ❳ (Ω, Ω) } • E 3 = {(X, Y ) ∈ 2 Ω × 2 Ω / Y = X ∪ {c}} = { (∅, {c}), ({a}, {a, c}), ({b}, {b, c}), ({a, b}, Ω), ✘ ✘ ✘ ✘ ✘ ❳ ❳ ❳ ❳ ❳ ({c}, {c}), ✭ ✭ ✭ ✭ ✭ ✭ ✭ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ({a, c}), {a, c}), ✭ ✭ ✭ ✭ ✭ ✭ ✭ ❤ ❤ ❤ ❤ ❤ ❤ ❤ ({b, c}, {b, c}), ✘ ✘ ✘ ❳ ❳ ❳ (Ω, Ω) } Fig.
h 3 (Ω) = f (Ω) + f ({b, c}) + f ({c}) + f ({a, c}) + f (∅) + f ({a}) + f ({b}) + f ({a, b}). Proposition 2.3.2. The dual of this particular sequence in (2 Ω , ⊇) is (H i ) i∈ 1,n , where H i = (2 Ω , E i ) and: E i = {(X, Y ) ∈ 2 Ω × 2 Ω / X = Y ∪ {ω i }}.
This sequence computes the same zeta transformations as

G ⊃ = (2 Ω , E ⊃ ), where E ⊃ = {(X, Y ) ∈ 2 Ω × 2 Ω / X ⊃ Y }.
Example 2.3.2. Fig. 2 illustrates the dual sequence for zeta transforms in (2 Ω , ⊇) and Ω = {a, b, c}.

Remark. This sequence computes the same zeta transformations as G⊃ = (2 Ω , E⊃), where

• • • • • • • • 1 : X = Y ∪ {a} • • • • • • • • 2 : X = Y ∪ {b} • • • • • • • • 3 : X = Y ∪ {c} • • • • • • • •
E⊃ = {(X, Y ) ∈ 2 Ω × 2 Ω / X ⊃ Y }.
transformation as respectively (G ⊂ , f, +) and (G ⊃ , f, +) for any function f : 2 Ω → R. The authors proved them to be the optimal transformations for any set Ω, i.e. the one that uses the fewest arrows, independently of the function f to be considered. This means that they do not take into account the neutral values of f for the operator +, i.e. where f evaluates to 0, contrary to our approach. This is why our method is able to feature a lower complexity than this optimal FMT.

More generally, Theorem 3 of [START_REF] Kennes | Computational aspects of the Mobius transformation of graphs[END_REF] defines a necessary and sufficient condition to verify that a transformation ((H i ) i∈ 1,n , f, +) computes (ignoring identity arrows) the same transformation as (G < , f, +). It is stated in our terms as follows:

Theorem 2.3.1. Let (H i ) i∈ 1,n be a sequence of directed acyclic graphs H i = (P, E i ). Let us pose A i = E i ∪ I P . The transformation ((H i ) i∈ 1,n , f, +) computes (ignoring identity arrows) the same transformation as (G < , f, +) if and only if each set of arrows satisfies E i ⊆ E ≤ and every arrow e ∈ E ≤ can be decomposed as a unique path (e 1 , e 2 , . . . , e

n ) ∈ A 1 × A 2 × • • • × A n ,
where the tail of e 1 is the tail of e and the head of e n is the head of e. Recall that a path is a sequence of arrows in which ∀i ∈ 1, n -1 , the head of e i is the tail of e i+1 .

Example 2.3.3. Let us prove Proposition 2.3.1. We had Ω = {ω 1 , ω 2 , . . . , ω n }. The sequence of graphs (H i ) i∈ 1,n computes the same zeta transformations as

G ⊂ = (2 Ω , E ⊂ ), where E ⊂ = {(X, Y ) ∈ 2 Ω × 2 Ω / X ⊂ Y } if: E i = {(X, Y ) ∈ 2 Ω × 2 Ω / Y = X ∪ {ω i }},
where i ∈ {1, . . . , n} and

H i = (2 Ω , E i ).
Proof. Obviously, for any i ∈ 1, n , we have E i ⊆ E ⊆ . In addition, each set X ⊆ Ω is composed by definition of at most n elements from Ω. Thus, it is possible to reach in at most n steps from X any set Y ⊆ Ω such that X ⊆ Y with identity arrows and arrows where the head is just the tail with exactly one other element from Ω, i.e. with identity arrows or arrows of (H i ) i∈ 1,n . Moreover, since each step corresponds to a distinct element from Ω, there is exactly one path from X to Y : at each step corresponding to the elements in Y \X, follow the arrow that adds an element to the set reached in the previous step. Only identity arrows can be followed in the steps corresponding to the elements in X ∩ Y . Otherwise, there would be an element missing or in excess relatively to Y at the end of step n, which means that Y could not be reached. Therefore, according to Theorem 2.3.1, the transformation ((H i ) i∈ 1,n , f, +) computes the same transformation as (G ⊂ , f, +) for any function f : 2 Ω → R.

In addition, for a sequence of graphs computing zeta transforms in (P, ≤), reversing its paths yields a sequence of graphs computing zeta transforms in (P, ≥). Hence Proposition 2.3.2.

Sequence of graphs and computation of the Möbius transform

Now, consider that we want to find a sequence of graphs that undoes the previous computation. We want to transform g into f , i.e. the Möbius transform of g in (P, ≤). For this, notice that for any step i in the transformation ((H i ) i∈ 1,n , f, +), we have for each node y ∈ P ,

h i (y) = h i-1 (y) + (x,y)∈Ei\IP h i-1 (x) ⇔ h i-1 (y) = h i (y) - (x,y)∈Ei\IP h i-1 (x).
So, as long as we know all h i-1 (x) for all arrows (x, y) ∈ E i \I P at each step i and for all y ∈ P , we can simply reverse the order of the sequence (H i ) i∈ 1,n and use the operator -instead of +. If this is verified, then ((H n-i+1 ) i∈ 1,n , g, -) computes the Möbius transform of g in (P, ≤). This condition can be translated as follows: for every arrow (x, y) ∈ E i \I P , we have h i (x) = h i-1 (x). This condition is equivalent to stating that for every arrow (x, y) ∈ E i \I P , there is no arrow (w, x) in E i \I P .

Theorem 2.4.1. Let (H i ) i∈ 1,n be a sequence of directed acyclic graphs H i = (P, E i ). Let h n be the function resulting from the transformation ((H i ) i∈ 1,n , f, +), ignoring identity arrows. If for every arrow (x, y) ∈ E i \I P , there is no arrow (w, x) in E i \I P , then ((H n-i+1 ) i∈ 1,n , h n , -) yields the initial function f . Thus, if ((H i ) i∈ 1,n , f, +) computes the zeta transform g of f in (P, ≤) and Theorem 2.4.1 is satisfied, then ((H n-i+1 ) i∈ 1,n , g, -) computes the Möbius transform f of g in (P, ≤).

Application to the powerset lattice 2 Ω (FMT)

Consider again the sequence (H i ) i∈ 1,n , from the application of section 2.3.1, that computes the zeta transform of f in (2 Ω , ⊆). If there is an arrow (X, Y ) ∈ E i \I 2 Ω , then ω i ∈ X. This means that there is no set W in 2 Ω such that W ∪ {ω i } = X, and so no arrow (W, X) in E i \I 2 Ω . Thus, according to Theorem 2.4.1, ((H n-i+1 ) i∈ 1,n , h n , -) computes the Möbius transformation of ((H i ) i∈ 1,n , f, +), i.e. the function f . Furthermore, given that Ω is a set and that each graph H i concerns an element ω i , independently from the others, any indexing (order) in the sequence (H i ) i∈ 1,n computes the zeta transformation. This implies that any order in ((H n-i+1 ) i∈ 1,n , h n , -) computes the Möbius transformation of ((H i ) i∈ 1,n , f, +). In particular, ((H i ) i∈ 1,n , h n , -) computes the same transformation as ((H n-i+1 ) i∈ 1,n , h n , -).

Example 2.4.1. Let us say that Ω = {a, b, c}. We want to compute the Möbius transform f of g in (2 Ω , ⊆). Each arrow set E i has already been computed in Example 2.3.1. Fig. 1 illustrates any transformation based on (H i ) i∈ 1,n , including ((H i ) i∈ 1,n , h n , -). Check that, after execution of ((H i ) i∈ 1,n , h n , -), each element y of 2 Ω is associated with f (y). For instance, let us take a look again at Ω. Initially, each element of 2 Ω is associated with its value through g. Then, at step 1, we can see that to the value on Ω is subtracted g({b, c}). At step 2, to h 1 (Ω) is subtracted h 1 ({a, c}), which is equal to g({a, c})g({c}), following step 1. Finally, at step 3, to h 2 (Ω) is subtracted h 2 ({a, b}), which is equal to h 1 ({a, b})h 1 ({a}) following step 2, which is itself equal to g({a, b})g({b}) -(g({a})g(∅)), following step 1. Gathering all these terms, we get that

h 3 (Ω) = g(Ω) -g({b, c}) -[ g({a, c}) -g({c}) ] -[ g({a, b}) -g({b}) -[ g({a}) -g(∅) ] ] = g(Ω) -g({b, c}) -g({a, c}) + g({c}) -g({a, b}) + g({b}) + g({a}) -g(∅) = X⊆Ω g(x).(-1) |Ω|-|X| .
As recalled in [START_REF] Kennes | Computational aspects of the Mobius transformation of graphs[END_REF], the function that associates to each couple (X, Y ) ∈ 2 Ω × 2 Ω the value (-1) |Y |-|X| is the Möbius function µ in (2 Ω , ⊆). So, according to Eq. 2, we have h 3 (Ω) = f (Ω).

Order theory

Let (P, ≤) be a set partially ordered by the relation ≤.

Meet / join

Let S be a subset of P . If it is unique, the greatest element of P that is less than all the elements of S is called the meet (or infimum) of S. It is noted S. If S = {x, y}, we may also note it with the binary operator ∧ such that x ∧ y. If it is unique, the least element of P that is greater than all the elements of S is called the join (or supremum) of S. It is noted S. If S = {x, y}, we may also note it with the binary operator ∨ such that x ∨ y.

Example 2.5.1. In (2 Ω , ⊆), the meet operator ∧ is the intersection operator ∩, while the join operator ∨ is the union operator ∪.

Lattice / semi-lattice

If any non-empty subset of P has a join, we say that P is an upper semilattice. If any non-empty subset of P has a meet, we say that P is a lower semilattice. When P is both, we say that P is a lattice.

Example 2.5.2. In (2 Ω , ⊆), any non-empty subset S has an intersection and a union in 2 Ω . They respectively represent the common elements of the sets in S and the cumulative elements of all the sets in S. Thus, 2 Ω is a lattice.

Irreducible elements

In any partially ordered set, there are bottom elements such that they cannot be described as the join of two lesser elements. Such irreducible elements are called the join-irreducible elements of P if they are not equal to the global minimum of P . We will note ∨ I(P ) the set of all join-irreducible elements of P . Since none of them is P , this means that the join of any two join-irreducible elements yields a non-join-irreducible element of P . In fact, if P is an upper semilattice (or a lattice), it is known that the join of all possible non-empty subset of ∨ I(P ) yields all elements of P , except P . Formally, we write that all join-irreducible element i verifies i = P and for all elements x, y ∈ P , if x < i and y < i, then x ∨ y < i.

Dually, in any partially ordered set, there are top elements such that they cannot be described as the meet of two greater elements. Such irreducible elements are called the meet-irreducible elements of P if they are not equal to the global maximum of P . We will note ∧ I(P ) the set of all meet-irreducible elements of P . Since none of them is P , this means that the meet of any two meet-irreducible elements yields a non-meet-irreducible element of P . In fact, if P is a lower semilattice (or a lattice), it is known that the meet of all possible non-empty subset of ∧ I(P ) yields all elements of P , except P . Formally, we write that all meet-irreducible element i verifies i = P and for all elements x, y ∈ P , if x > i and y > i, then x ∧ y > i.

Example 2.5.3. In (2 Ω , ⊆), the join-irreducible elements are the singletons {ω}, where ω ∈ Ω. The meet-irreducible elements are their complement {ω} = Ω\{ω}, where ω ∈ Ω.

Distributive lattice

A distributive lattice L is a lattice that satisfies the distributive law:

∀x, y, z ∈ L, (x ∧ y) ∨ (x ∧ z) = x ∧ (y ∨ z) (3) Since (x ∧ z) ∨ z = z, this condition is equivalent to: ∀x, y, z ∈ L, (z ∨ y) ∧ (z ∨ x) = z ∨ (y ∧ x) (4)
Example 2.5.4. In the powerset lattice 2 Ω , it holds for any sets

A, B, C ∈ 2 Ω that (A ∩ B) ∪ (A ∩ C) = A ∩ (B ∪ C).
Thus, the lattice 2 Ω is a distributive lattice.

Sublattice

A sublattice S is simply a subset of a lattice L that is itself a lattice, with the same meet and join operations as L. This means that for any two elements x, y ∈ S, we have both x ∨ y ∈ S and x ∧ y ∈ S, where ∨ and ∧ are the join and meet operators of L.

Upset / down set

An upset (or upward closed set) S is a subset of P such that all elements in P greater than at least one element of S is in S. The upper closure of an element x ∈ P is noted ↑ x or x ↑P (when the encompassing set has to be specified). It is equal to {y ∈ P / x ≤ y }.

Dually, a down set (or downward closed set) S is a subset of P such that all elements in P less than at least one element of S is in S. The lower closure of an element x ∈ P is noted ↓ x or x ↓P (when the encompassing set has to be specified). It is equal to {y ∈ P / x ≥ y }.

Support elements and focal points

Let f : P → R.

Support of a function in P

The support supp(f ) of a function f :

P → R is defined as supp(f ) = {x ∈ P / f (x) = 0}.
Example 2.6.1. In DST, the set containing the focal sets of a mass function m is supp(m).

Focal points

We note ∨ supp(f ) the smallest join-closed subset of P containing supp(f ), i.e.:

∨ supp(f ) = S / S ⊆ supp(f ), S = ∅
We note ∧ supp(f ) the smallest meet-closed subset of P containing supp(f ), i.e.:

∧ supp(f ) = S / S ⊆ supp(f ), S = ∅
The set containing the focal points F of a mass function m from [START_REF] Chaveroche | Calcul exact de faible complexité des décompositions conjonctive et disjonctive pour la fusion d'information[END_REF][START_REF]Efficient exact computation of the conjunctive and disjunctive decompositions of D-S Theory for information fusion: Translation and extension[END_REF] for the conjunctive weight function is ∧ supp(m). For the disjunctive weight function, we use their dual focal points, defined by ∨ supp(m).

It has been proven in [START_REF] Chaveroche | Calcul exact de faible complexité des décompositions conjonctive et disjonctive pour la fusion d'information[END_REF][START_REF]Efficient exact computation of the conjunctive and disjunctive decompositions of D-S Theory for information fusion: Translation and extension[END_REF] that the image of 2 Ω through the conjunctive weight function can be computed without redundancies by only considering the focal points ∧ supp(m) in the definition of the multiplicative Möbius transform of the commonality function. The image of all set in 2 Ω \ ∧ supp(m) through the conjunctive weight function is 1. In the same way, the image of any set in 2 Ω \ ∧ supp(m) through the commonality function is only a duplicate of the image of a focal point in ∧ supp(m). Its image can be recovered by searching for its smallest focal point superset in ∧ supp(m). The same can be stated for the disjunctive weight function regarding the implicability function and ∨ supp(m).

In fact, as generalized in [START_REF] Chaveroche | Focal points and their implications for möbius transforms and dempster-shafer theory[END_REF], for any function f : P → R, its focal points ∧ supp(f ) are sufficient to define its zeta and Möbius transforms in (P, ≥), and ∨ supp(f ) is sufficient to define its zeta and Möbius transforms in (P, ≤).

However, considering the case where P is a finite lattice, naive algorithms that only consider o supp(f ), where o ∈ {∨, ∧} have upper bound complexities in O(| o supp(f )| 2 ), which may be worse than the optimal complexity O(| ∨ I(P )|.|P |) of a procedure that considers the whole lattice P . In this paper, we propose computing schemes for g(S), where o supp(f ) ⊆ S ⊆ P and g is the zeta transform of f in (P, ≤), with complexities always less than O(| ∨ I(P )|.|P |), provided that P is a finite distributive lattice. We also provide schemes for computing the Möbius transform f (S) of g in (P, ≤).

Our Efficient Möbius Transformations

In this section, we consider a function f : P → R where P is a finite distributive lattice (e.g. the powerset lattice 2 Ω ). We present here the sequences of graphs that can be exploited to compute our so-called Efficient Möbius Transformations. Theorem 3.2.1 describes a way of computing the zeta and Möbius transforms of a function based on the smallest sublattice L supp(f ) of P containing both ∧ supp(f ) and ∨ supp(f ), which is defined in Proposition 3.1.3. Theorem 3.2.2 goes beyond this optimization by computing these transforms based only on o supp(f ), where o ∈ {∨, ∧}. Nevertheless, this second approach requires the direct computation of o supp(f ), which has an upper bound complexity of

O(|supp(f )|.| o supp(f )|), which may be more than O(| ∨ I(P )|.|P |) if |supp(f )| ≫ | ∨ I(P )|.

Preliminary results

In this subsection, we provide some propositions that are useful for proving our main results (presented in the next subsection). Lemma 3.1.1 (Safe join). Let us consider a finite distributive lattice L. For all join-irreducible element i ∈ ∨ I(L) and for all elements x, y ∈ L that are not greater than or equal to i, i.e. i ≤ x and i ≤ y, we have that their join is not greater or equal to i either, i.e. i ≤ x ∨ y.

Proof. By definition of a join-irreducible element, we know that ∀i ∈ ∨ I(L) and for all a, b ∈ L, if a < i and b < i, then a ∨ b < i. Moreover, for all x, y ∈ L such that i ≤ x and i ≤ y, we have equivalently i ∧ x < i and i ∧ y < i. Thus, we get that (i ∧ x) ∨ (i ∧ y) < i. Since L satisfies the distributive law Eq. ( 3), this implies that (i ∧ x) ∨ (i ∧ y) = i ∧ (x ∨ y) < i, which means that i ≤ x ∨ y. Lemma 3.1.2 (Safe meet ). Let us consider a finite distributive lattice L. For all meetirreducible element i ∈ ∧ I(L) and for all elements x, y ∈ L that are not less than or equal to i, i.e. i ≥ x and i ≥ y, we have that their meet is not less or equal to i either, i.e. i ≥ x ∧ y.

Proof. By definition of a meet-irreducible element, we know that ∀i ∈ ∧ I(L) and for all a, b ∈ L, if a > i and b > i, then a ∧ b > i. Moreover, for all x, y ∈ L such that i ≥ x and i ≥ y, we have equivalently i ∨ x > i and i ∨ y > i. Thus, we get that (i ∨ x) ∧ (i ∨ y) > i. Since L satisfies the distributive law Eq. ( 4), this implies that (i ∨ x) ∧ (i ∨ y) = i ∨ (x ∧ y) < i, which means that i ≥ x ∨ y. Proposition 3.1.1 (Iota elements of a subset of P ). For any subset S ⊆ P , we note ι(S) the set containing the join-irreducible elements of the smallest sublattice L S of P containing S, i.e. ι(S) = ∨ I(L S ). These so-called iota elements of S can be obtained through the following equality:

ι(S) = i ↑S / i ∈ ∨ I(P ), i ↑S = ∅ ,
where i ↑S is the upper closure of i in S, i.e. {s ∈ S / i ≤ s}.

Proof. See Appendix A.1.

Proposition 3.1.2 (Dual iota elements of a subset of P ). Similarly, for any subset S ⊆ P , we note ι(S) the set containing the meet-irreducible elements of the smallest sublattice L S of P containing S, i.e. ι(S) = ∧ I(L S ). These so-called dual iota elements of S can be obtained through the following equality:

ι(S) = i ↓S / i ∈ ∧ I(P ), i ↓S = ∅ ,
where i ↓S is the lower closure of i in S, i.e. {s ∈ S / i ≥ s}.

Proof. Analog to the proof of Proposition 3.1.1, exploiting the dual definition of the distributive law in a lattice, i.e. Eq. (4). Proposition 3.1.3 (Lattice support ). The smallest sublattice of P containing both ∧ supp(f ) and ∨ supp(f ), noted L supp(f ), can be defined as:

L supp(f ) = X / X ⊆ ι(supp(f )), X = ∅ ∪ supp(f ) = X / X ⊆ ι(supp(f )), X = ∅ ∪ supp(f ) . More specifically, ∨ supp(f ) is contained in the upper closure supp(f ) ↑ L supp(f ) of supp(f ) in L supp(f ): supp(f ) ↑ L supp(f ) = {x ∈ L supp(f ) / ∃s ∈ supp(f ), s ≤ x},
and ∧ supp(f ) is contained in the lower closure supp(f ) ↓ L supp(f ) of supp(f ) in L supp(f ): supp(f ) ↓ L supp(f ) = {x ∈ L supp(f ) / ∃s ∈ supp(f ), s ≥ x}.
These sets can be computed in less than respectively O(|ι(supp(f

))|.|supp(f ) ↑ L supp(f ) |) and O(|ι(supp(f ))|.|supp(f ) ↓ L supp(f ) |), which is at most O(| ∨ I(P )|.|P |).
Proof. The proof is immediate here, considering Proposition 3.1.1 and its proof, as well as Proposition 3.1.2. In addition, since ∧ supp(f ) only contains the meet of elements of supp(f ), all element of ∧ supp(f ) is less than at least one element of supp(f ). Similarly, since ∨ supp(f ) only contains the join of elements of supp(f ), all element of ∨ supp(f ) is greater than at least one element of supp(f ). Hence supp(f )

↑ L supp(f ) and supp(f ) ↓ L supp(f ) .
As pointed out in [START_REF] Kaski | Fast Möbius inversion in semimodular lattices and U-labelable posets[END_REF], a special ordering of the join-irreducible elements of a lattice when using the Fast Zeta Transform [START_REF] Björklund | Fast zeta transforms for lattices with few irreducibles[END_REF] leads to the optimal computation of its zeta and Möbius transforms. Here, we use this ordering to build our EMT for finite distributive lattices in a way similar to [START_REF] Kaski | Fast Möbius inversion in semimodular lattices and U-labelable posets[END_REF] but without the need to check the equality of the decompositions into the first j join-irreducible elements at each step.

Corollary 3.1.1 (Join-irreducible ordering). Let us consider a finite distributive lattice (L, ≤) and let its join-irreducible elements ∨ I(L) be ordered such that ∀i k , i l

∈ ∨ I(L), k < l ⇒ i k ≥ i l .
If L is a graded lattice (i.e. a lattice equipped with a rank function ρ :

L → N), then ρ(i 1 ) ≤ ρ(i 2 ) ≤ • • • ≤ ρ(i | ∨ I(L)| ) implies this ordering. We note ∨ I(L) k = {i 1 , . . . , i k-1 , i k }. For all element i k ∈ ∨ I(L), we have i k ≤ ∨ I(L) k-1 .
Proof. Since the join-irreducible elements are ordered such that ∀i k , i l ∈ ∨ I(L), k < l ⇒ i k ≥ i l , it is trivial to see that for any i l ∈ ∨ I(L) and i k ∈ ∨ I(L) l-1 , we have i k ≥ i l . Then, using Lemma 3.1.1 by recurrence, it is easy to get that i l ≤ ∨ I(L) l-1 .

Example 3.1.1. For example, in DST we work with P = 2 Ω , in which the rank function is the cardinality, i.e. for all A ∈ P , ρ(A) = |A|. So, with (L, ⊆) a subset lattice of (2 Ω , ⊆), the ordering required in Corollary 3.1.1 simply translates to sorting the join-irreducible elements of L from the smallest set to the largest set. Thus, sorting

∨ I(L) = {i 1 , i 2 , • • • , i n } such that |i 1 | ≤ |i 2 | ≤ • • • ≤ |i n |, Corollary 3.1.1 tells us that for any k ∈ 2, n , we have i k ⊆ ∨ I(L) k-1 , where ∨ I(L) k = {i 1 , . . . , i k-1 , i k }. Corollary 3.1.2 (Meet-irreducible ordering). Let us consider a finite distributive lattice (L, ≤) and let its meet-irreducible elements ∧ I(L) be ordered such that ∀i k , i l ∈ ∨ I(L), k < l ⇒ i k ≤ i l .
If L is a graded lattice (i.e. a lattice equipped with a rank function ρ :

L → N), then ρ(i 1 ) ≥ ρ(i 2 ) ≥ • • • ≥ ρ(i | ∧ I(L)| ) implies this ordering. We note ∧ I(L) k = {i 1 , . . . , i k-1 , i k }. For all element i k ∈ ∧ I(L), we have i k ≥ ∧ I(L) k-1 .
Proof. Since the meet-irreducible elements are ordered such that ∀i k , i l ∈ ∧ I(L), k < l ⇒ i k ≤ i l , it is trivial to see that for any i l ∈ ∧ I(L) and i k ∈ ∧ I(L) l-1 , we have i k ≤ i l . Then, using Lemma 3.1.2 by recurrence, it is easy to get that i l ≥ ∧ I(L) l-1 .

I(L) = {i 1 , i 2 , • • • , i n } such that |i 1 | ≥ |i 2 | ≥ • • • ≥ |i n |, Corollary 3.1.2 tells us that for any k ∈ 2, n , we have i k ⊇ ∧ I(L) k-1 , where ∧ I(L) k = {i 1 , . . . , i k-1 , i k }.

Main results

In this subsection, we present our two types of transformations computing the zeta and Möbius transforms of a function f : P → R. The first one corresponds to Theorem 3.2.1 and its corollaries and is based on a sublattice L ⊆ P , where L contains the lattice support of f , i.e. L supp(f ) ⊆ L. The second one corresponds to Theorem 3.2.2 and its corollary and is based on any lower subsemilattice of P containing ∧ supp(f ). Its dual is presented in Corollary 3.2.7 and its corollary and is based on any upper subsemilattice of P containing ∨ supp(f ).

∅ {a} {d} {a,d} {c,d,f} {a,c,d,f} Ω • • • • • • • 1 : Y = X ∪ Ω • • • • • • • 2 : Y = X ∪ {c, d, f } • • • • • • • 3 : Y = X ∪ {d} • • • • • • • 4 : Y = X ∪ {a} • • • • • • • Figure 3:
Illustration representing the paths generated by the arrows contained in the sequence (H k ) k∈ 1,4 , where

H k = (L, E k ) and E k = {(X, Y ) ∈ L 2 / Y = X ∪ i 5-k } and L = {∅, {a}, {d}, {a, d}, {c, d, f }, {a, c, d, f }, Ω} and Ω = {a, b, c, d, e, f } and (i k ) k∈ 1,4 = ({a}, {d}, {c, d, f }, Ω)
. This sequence computes the same zeta transformations as G⊂ = (L, E⊂), where

E⊂ = {(X, Y ) ∈ L 2 / X ⊂ Y }. ∅ {a} {d} {a,d} {c,d,f} {a,c,d,f} Ω • • • • • • • 1 : Y = X ∪ {a} • • • • • • • 2 : Y = X ∪ {d} • • • • • • • 3 : Y = X ∪ {c, d, f } • • • • • • • 4 : Y = X ∪ Ω • • • • • • • -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
(L) = {i 1 , i 2 , • • • , i n } be ordered such that ∀i k , i l ∈ ∨ I(L), k < l ⇒ i k ≥ i l .
Consider the sequence (H k ) k∈ 1,n , where H k = (L, E k ) and:

E k = (x, y) ∈ L 2 / y = x ∨ i n+1-k .
This sequence computes the same zeta transformations as

G < = (L, E < ), where E < = {(X, Y ) ∈ L 2 / X < Y }.
E k = (x, y) ∈ L 2 / x = y ∧ i k .
with the meet-irreducible elements , where

∧ I(L) = {i 1 , i 2 , • • • , i n } ordered such that ∀i k , i l ∈ ∧ I(L), ∅ {a} {d} {a,d} {c,d,f} {a,c,d,f} Ω • • • • • • • 1 : X = Y ∪ {a} • • • • • • • 2 : X = Y ∪ {d} • • • • • • • 3 : X = Y ∪ {c, d, f } • • • • • • • 4 : X = Y ∪ Ω • • • • • • •
H k = (L, E k ) and E k = {(X, Y ) ∈ L 2 / X = Y ∪ i k } and L = {∅,
E⊃ = {(X, Y ) ∈ L 2 / X ⊃ Y }. k < l ⇒ i k ≤ i l , i.e.
E k = (x, y) ∈ L 2 / y = x ∨ i k .
This sequence computes the same Möbius transformations as

G < = (L, E < ), where E < = {(X, Y ) ∈ L 2 / X < Y }.
This sequence is illustrated in Fig. 4 and leads to the same complexities as the one presented in Theorem 3.2.1.

Proof. For every arrow (x, y) ∈ E k , if i k ≤ x, then there is an arrow such that y = x ∨ i k = x. However, there can be no arrow (w, x) ∈ E k since x cannot be equal to w ∨ i k . Otherwise, if i k ≤ x, then y = x∨i k = x, i.e. (x, y) is an identity arrow. Thus, for every arrow (x, y) ∈ E k \I P , there is no arrow (w, x) in E k \I P , meaning that Theorem 2.4.1 is satisfied. The sequence (H n-k+1 ) k∈ 1,n computes the same Möbius transformations as G < .

Corollary 3.2.3. Again, it can be shown similarly that the sequence (H k ) k∈ 1,n computes the same Möbius transforms as the sequence of Corollary 3.2.2, where H k = (L, E k ) and:

E k = (x, y) ∈ L 2 / x = y ∧ i n+1-k . with the meet-irreducible elements ∧ I(L) = {i 1 , i 2 , • • • , i n } ordered such that ∀i k , i l ∈ ∧ I(L), k < l ⇒ i k ≤ i l , i.e.
E k = (x, y) ∈ L 2 / x = y ∨ i k .
This sequence computes the same zeta transformations as

G > = (L, E > ), where E > = {(X, Y ) ∈ L 2 / X > Y }.
This sequence is illustrated in Fig. 5 and leads to the same complexities as its dual.

Corollary 3.2.5. Consider the sequence (H k ) k∈ 1,n , where H k = (L, E k ) and:

E k = (x, y) ∈ L 2 / x = y ∨ i n+1-k .
This sequence computes the same Möbius transformations as

G > = (L, E > ), where E > = {(X, Y ) ∈ L 2 / X > Y }.
This sequence is illustrated in Fig. 6 and leads to the same complexities as the one presented in Theorem 3.2.1. Yet, we can reduce this complexity even further if we have ∧ supp(f ) or ∨ supp(f ). This is the motivation behind the sequence proposed in the following Theorem 3.2.2. As a matter of fact, [START_REF] Björklund | Fast zeta transforms for lattices with few irreducibles[END_REF] proposed a meta-procedure producing an algorithm that computes the zeta and Möbius transforms in an arbitrary intersection-closed family F of sets of 2 Ω with a circuit of size O(|Ω|.|F |). However, this meta-procedure is O(|Ω|.2 |Ω| ). Here, Theorem 3.2.2 provides a sequence of graphs that leads to procedures that directly compute the zeta and Möbius transforms in O(|Ω|.|F |.ǫ), where ǫ can be as low as 1. Besides, our method is far more general since it applies to any meet-closed or join-closed subset of a finite distributive lattice. The intuition behind it is that we can do the same computations as in Theorem 3.2.1, even in a subsemilattice, simply by bridging gaps, from the smallest gap to the biggest to make sure that all nodes are visited.

∅ {a} {d} {a,d} {c,d,f} {a,c,d,f} Ω • • • • • • • 1 : X = Y ∪ Ω • • • • • • • 2 : X = Y ∪ {c, d, f } • • • • • • • 3 : X = Y ∪ {d} • • • • • • • 4 : X = Y ∪ {a} • • • • • • • -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Theorem 3.2.2 (Efficient Möbius Transformation in a join-closed or meet-closed subset of P ). Let us consider a meet-closed subset M of P (such as ∧ supp(f )). Also, let the iota elements

ι(M ) = {i 1 , i 2 , • • • , i n } be ordered such that ∀i k , i l ∈ ι(M ), k < l ⇒ i k ≥ i l .
Consider the sequence (H k ) k∈ 1,n , where H k = (M, E k ) and:

E k = (x, y) ∈ M 2 / x = (y ∨ i k ) ↑M and x ≤ y ∨ ι(M ) k ,
where ι(M ) k = {i 1 , i 2 , . . . , i k }. This sequence computes the same zeta transformations as Remark. This number ǫ is hard to evaluate beforehand since it depends on both the number of "gaps to bridge" and the average number of elements that can be greater than some element.

G > = (M, E > ), where E > = {(X, Y ) ∈ M 2 / X > Y }.
∅ {a} {b} {a,b} {c} {d} {b,c,d} Ω • • • • • • • • 1 : X = (Y ∪ {a}) ↑M and X ⊆ Y ∪ {a} • • • • • • • • 2 : X = (Y ∪ {b}) ↑M and X ⊆ Y ∪ {a, b} • • • • • • • • 3 : X = (Y ∪ {c}) ↑M and X ⊆ Y ∪ {a, b, c} • • • • • • • • 4 : X = (Y ∪ {d}) ↑M and X ⊆ Y ∪ {a, b, c, d} • • • • • • • • 5 : X = (Y ∪ Ω) ↑M and X ⊆ Y ∪ Ω • • • • • • • • Figure 7:
Illustration representing the paths generated by the arrows contained in the sequence (H k ) k∈ 1,5 , where

H k = (M, E k ) and E k = (X, Y ) ∈ M 2 / X = (Y ∪ i k ) ↑M and X ⊆ Y ∪ ι(M ) k
and ι(M ) k = {i1, i2, . . . , i k } and M = {∅, {a}, {b}, {a, b}, {c}, {d}, {b, c, d}, Ω} and Ω = {a, b, c, d, e, f } and (i k ) k∈ 1,5 = ({a}, {b}, {c}, {d}, Ω). This sequence computes the same zeta transformations as G⊃ = (M, E⊃), where E⊃ = {(X, Y ) ∈ M 2 / X ⊃ Y }. Actually, since there is no order between any two iota elements of ι(M )\{Ω} in this example, the order chosen here is arbitrary. Any order would compute the same zeta transformations as G⊃, as long as Ω is the last iota element to consider.

If there is no gap, or if there is only one greater element, this ǫ can be as low as 1. Moreover, the choice of data structures may greatly reduce this ǫ. For instance, if P = 2 Ω , then dynamic binary trees may be employed to avoid the consideration of elements that cannot be less than some already found element in (y ∪ i k ) ↑M , by cutting some branches. Corollary 3.2.6. Consider the sequence (H k ) k∈ 1,n , where H k = (M, E k ) and:

E k = (x, y) ∈ M 2 / x = (y ∨ i n+1-k ) ↑M and x ≤ y ∨ ι(M ) n+1-k .
This sequence computes the same Möbius transformations as

G > = (M, E > ), where E > = {(X, Y ) ∈ M 2 / X > Y }.
This sequence is illustrated in Fig. 8 and leads to the same complexities as the one presented in Theorem 3.2.2.

Proof. Analog to the proof of Corollary 3.2.2.

Corollary 3.2.7. Dually, let us consider a join-closed subset J of P (such as ∨ supp(f )). Also, let the dual iota elements ι(J) = {i 1 , i 2 , • • • , i n } be ordered such that ∀i k , i l ∈ ι(J), k < l ⇒ i k ≤ i l , i.e. in reverse order compared to the iota elements of Theorem 3.2.2.

In the direct line of Corollary 3.2.1, consider the sequence (H k ) k∈ 1,n , where H k = (J, E k ) and:

E k = (x, y) ∈ J 2 / x = (y ∧ i k ) ↓J and x ≥ y ∧ ι(J) k ,
where ι(J) k = {i 1 , i 2 , . . . , i k }. This sequence computes the same zeta transformations as

G < = (J, E < ), where E < = {(X, Y ) ∈ J 2 / X < Y }.
Ω • • • • • • • • 1 : X = (Y ∪ Ω) ↑M and X ⊆ Y ∪ Ω • • • • • • • • 2 : X = (Y ∪ {d}) ↑M and X ⊆ Y ∪ {a, b, c, d} • • • • • • • • 3 : X = (Y ∪ {c}) ↑M and X ⊆ Y ∪ {a, b, c} • • • • • • • • 4 : X = (Y ∪ {b}) ↑M and X ⊆ Y ∪ {a, b} • • • • • • • • 5 : X = (Y ∪ {a}) ↑M and X ⊆ Y ∪ {a} • • • • • • • • -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 Figure 8:
Illustration representing the paths generated by the arrows contained in the sequence (H k ) k∈ 1,5 , where

H k = (M, E k ) and E k = (X, Y ) ∈ M 2 / X = (Y ∪ i 6-k ) ↑M and X ⊆ Y ∪ ι(M ) 6-k
and ι(M ) k = {i1, i2, . . . , i k } and M = {∅, {a}, {b}, {a, b}, {c}, {d}, {b, c, d}, Ω} and Ω = {a, b, c, d, e, f } and (i k ) k∈ 1,5 = ({a}, {b}, {c}, {d}, Ω). This sequence computes the same Möbius transformations as G⊃ = (M, E⊃), where E⊃ = {(X, Y ) ∈ M 2 / X ⊃ Y }. The "-1" labels emphasize the intended use of the operatorwith this sequence. Actually, since there is no order between any two iota elements of ι(M )\{Ω} in this example, the order chosen in Fig. 7 is arbitrary. Thus, any order here would compute the same Möbius transformations as G⊃, as long as Ω is the first iota element to consider.

where H k = (J, E k ) and:

E k = (x, y) ∈ J 2 / x = (y ∧ i n+1-k ) ↓J and x ≥ y ∧ ι(J) n+1-k .
This sequence computes the same Möbius transformations as G < = (J, E < ), where E < = {(X, Y ) ∈ J 2 / X < Y }. This sequence is illustrated in Fig. 10 and leads to the same complexities as the one presented in Corollary 3.2.7. Let us take the sequence (H k ) k∈ 1,n from Theorem 3.2.2, where H k = ( ∧ supp(f ), E k ) and:

Discussions

E k = (x, y) ∈ ∧ supp(f ) 2 / x = (y ∨ i k ) ↑ ∧ supp(f ) and x ≤ y ∨ ι( ∧ supp(f )) k , where ι( ∧ supp(f )) k = {i 1 , i 2 , . . . , i k } such that ∀i k , i l ∈ ι( ∧ supp(f )), k < l ⇒ i k ≥ i l .
Ω • • • • • • • • 1 : X = (Y ∩ {b, c, d, e, f }) ↓J and X ⊇ Y ∩ {b, c, d, e, f } • • • • • • • • 2 : X = (Y ∩ {a, c, d, e, f }) ↓J and X ⊇ Y ∩ {c, d, e, f } • • • • • • • • 3 : X = (Y ∩ {a, b, d, e, f }) ↓J and X ⊇ Y ∩ {d, e, f } • • • • • • • • 4 : X = (Y ∩ {a, b, c, e, f }) ↓J and X ⊇ Y ∩ {e, f } • • • • • • • • 5 : X = (Y ∩ ∅) ↓J and X ⊇ Y ∩ ∅ • • • • • • • • Figure 9:
Illustration representing the paths generated by the arrows contained in the sequence (H k ) k∈ 1,5 , where ,c,d,e,f },{a,c,d,e,f },{a,b,d,e,f },{a,b,c,e,f },∅). This sequence computes the same zeta transformations as G⊂ = (J, E⊂), where E⊂ = {(X, Y ) ∈ J 2 / X ⊂ Y }. Actually, since there is no order between any two dual iota elements of ι(J)\{∅} in this example, the order chosen here is arbitrary. Any order would compute the same zeta transformations as G⊂, as long as ∅ is the last dual iota element to consider. Let us now take the sequence (H k ) k∈ 1,n from Corollary 3.2.7, where H k = ( ∨ supp(f ), E k ) and:

H k = (J, E k ) and E k = (X, Y ) ∈ J 2 / X = (Y ∩ i k ) ↓J and X ⊇ Y ∩ ι(J) k and ι(J) k = {i1,
E k = (x, y) ∈ ∨ supp(f ) 2 / x = (y ∧ i k ) ↓ ∨ supp(f ) and x ≥ y ∧ ι( ∨ supp(f )) k , where ι( ∨ supp(f )) k = {i 1 , i 2 , . . . , i k } and such that ∀i k , i l ∈ ι( ∨ supp(f )), k < l ⇒ i k ≤ i l .
Ω • • • • • • • • 1 : X = (Y ∩ ∅) ↓J and X ⊇ Y ∩ ∅ • • • • • • • • 2 : X = (Y ∩ {a, b, c, e, f }) ↓J and X ⊇ Y ∩ {e, f } • • • • • • • • 3 : X = (Y ∩ {a, b, d, e, f }) ↓J and X ⊇ Y ∩ {d, e, f } • • • • • • • • 4 : X = (Y ∩ {a, c, d, e, f }) ↓J and X ⊇ Y ∩ {c, d, e, f } • • • • • • • • 5 : X = (Y ∩ {b, c, d, e, f }) ↓J and X ⊇ Y ∩ {b, c, d, e, f } • • • • • • • • -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Figure 10:

Illustration representing the paths generated by the arrows contained in the sequence (H k ) k∈ 1,5 , where {a, e, f }, {c, d, e, f }, {a, c, d, e, f }, {a, b, c, e, f }, {a, b, d, e, f }, {b, c, d, e, f }, Ω} andΩ = {a, b, c, d, e, f } and(i k ) k∈ 1, 5 = ({b,c,d,e,f },{a,c,d,e,f },{a,b,d,e,f },{a,b,c,e,f },∅). This sequence computes the same Möbius transformations as G⊂ = (J, E⊂), where E⊂ = {(X, Y ) ∈ J 2 / X ⊂ Y }. The "-1" labels emphasize the intended use of the operatorwith this sequence. Actually, since there is no order between any two dual iota elements of ι(J)\{∅} in this example, the order chosen in Fig. 9 is arbitrary. Thus, any order would compute the same Möbius transformations as G⊂, as long as ∅ is the first dual iota element to consider.

H k = (J, E k ) and E k = (X, Y ) ∈ J 2 / X = (Y ∩ i 6-k ) ↓J and X ⊇ Y ∩ ι(J) 6-k and ι(J) k = {i1, i2, . . . , i k } and J = {∅,

Moreover, supp(f )

↓ L supp(f ) can be optimized if Ω ∈ supp(f ). Indeed, in this case, we have supp(f ) ↓ L supp(f ) = L supp(f ), while there may be a lot less elements in (supp(f )\{Ω}) ↓ L supp(f ) .

If so, one can equivalently compute the down set (supp(f )\{Ω}) ↓ L supp(f ) , execute an EMT with Theorem 3.2.1, and then add the value on Ω to the value on all sets of (supp(f )\{Ω}) ↓ L supp(f ) .

The same can be done with (supp(f )\{∅}) ↑ L supp(f ) . This trick can be particularly useful in the case of the conjunctive and disjunctive weight function, which require that supp(f ) contains respectively Ω and ∅. Also, optimizations built for the FMT, such as the reduction of Ω to the core C or its optimal coarsened version Ω ′ , are already encoded in the use of the function ι (see Example 4.2.1). On the other hand, optimizations built for the evidence-based approach, such as approximations by reduction of the number of focal sets, i.e. reducing the size of supp(f ), can still greatly enhance the EMT.

Finally, it was proposed in [START_REF] Kennes | Computational aspects of the Mobius transformation of graphs[END_REF] to fuse two mass functions m 1 and m 2 using Dempster's rule by computing the corresponding commonality functions q 1 and q 2 in O(|Ω|.2 |Ω| ), then computing q 12 = q 1 .q 2 in O(2 |Ω| ) and finally computing back the fused mass function m 12 from q 12 in O(|Ω|.2 |Ω| ). Here, we propose to compute the same detour but only on the elements of supp(m 12 ) ⊆ (supp(m 1 ) ∪ supp(m 2 )) ↓ L supp(f ) . Indeed, notice that supp(m 12 ) ⊆ ∧ (supp(m 1 ) ∪ supp(m 2 )), which implies that supp(m 12 )

↓ L supp(f ) ⊆ (supp(m 1 ) ∪ supp(m 2 )) ↓ L supp(f ) .
Thus, noting L = (supp(m 1 ) ∪ supp(m 2 )) ↓ L supp(f ) , we compute the corresponding commonality functions q 1 and q 2 in O(|ι(L)|.|L|), then compute q 12 = q 1 .q 2 in O(|L|) and finally compute back the fused mass function

m 12 from q 12 in O(|ι(L)|.|L|), where ι(L) = ι(supp(m 1 ) ∪ supp(m 2 )). Example 4.2.1 (Coarsening in the consonant case). Let supp(f ) = {F 1 , F 2 , . . . , F K } such that F 1 ⊂ F 2 ⊂ • • • ⊂ F K . A coarsening Ω ′ of
Ω is a mapping from disjoint groups of elements of Ω to elements of Ω ′ . The set Ω ′ can be seen as a partition of Ω. The goal of this coarsening of Ω is to provide a reduced powerset 2 Ω ′ . The best coarsening in this example would create as much elements in Ω ′ as there are elements in supp(f ). Thus, the best coarsening would give us a powerset of size 2 |supp(f )| .

On the other hand, our iota elements ι(supp(f )) are the join-irreducible elements of the smallest sublattice of 2 Ω containing supp(f ). This lattice is what we called the lattice support of f and noted L supp(f ). By definition, we necessarily have | L supp(f )| ≤ 2 |supp(f )| . More precisely here, all elements of supp(f ) are both focal points and join-irreducible elements of L supp(f ), i.e. ι(supp(f )) = supp(f ) = ∨ supp(f ) = ∧ supp(f ), if ∅ ∈ supp(f ) (Otherwise, we have ι(supp(f )) = supp(f )\{∅}). In fact, since our iota elements are not mapped elements of a reduced set Ω ′ but instead raw sets from 2 Ω , combinations of joins lead to a vastly different lattice. In this example, we have L supp(f ) = supp(f ), instead of the 2 supp(f ) given by coarsening.

Conclusion

In this paper, we proposed the Efficient Möbius Transformations (EMT), which are general procedures to compute the zeta and Möbius transforms of any function defined on any finite distributive lattice with optimal complexity. They are based on our reformulation of the Möbius inversion theorem with focal points only, featured in our previous work [START_REF] Chaveroche | Focal points and their implications for möbius transforms and dempster-shafer theory[END_REF]. The EMT optimally exploit the information contained in both the support of this function and the structure of distributive lattices. Doing so, the EMT always perform better than the optimal complexity for an algorithm considering the whole lattice, such as the FMT. Following these findings, it remains to propose explicit algorithms and implementation guidelines. We provide this for the powerset lattice, for DST, in Appendix B. We plan to release both a C++ (roughly presented in Appendix) and a Python open-source DST implementation in the near future.

Appendices A Proofs about the Efficient Möbius Transformations

A.1 Proposition 3.1.1

Proof. Let us define L S as the set containing the join of all combinations of iota elements of S, in addition to . Formally, we have:

L S = X / X ⊆ ι(S), X = ∅ ∪ S .
By construction, we already know that the join of any number (except 0) of elements from L S is also in L S . So, L S is an upper-subsemilattice of P . In the following, we will prove that it is also a lower-subsemilattice of P .

But, before anything, notice that • ↑S : P → P is a closure operator, i.e. for any elements x, y ∈ P , we have:

x ≤ x ↑S (5)
x

≤ y ⇒ x ↑S ≤ y ↑S (6)
x

↑S ↑S = x ↑S (7)
Now, consider the meet of two iota elements ι 1 ∧ ι 2 , where ι 1 , ι 2 ∈ ι(S). By definition, there are two join-irreducible elements x, y ∈ ∨ I(P ) such that ι 1 ∧ ι 2 = x ↑S ∧ y ↑S = (x ↑S ∪ y ↑S ). Let us note δ = (x ↑S ∪ y ↑S ). Since S ⊇ x ↑S ∪ y ↑S , we know that S ≤ δ. If δ = S, then δ ∈ L S . Otherwise, given that P is a lattice, we know that δ is equal to the join of all the join-irreducible elements of P that are less than δ, i.e. δ ↓ ∨ I(P ) = δ.

For all join-irreducible elements i ∈ δ ↓ ∨ I(P ) , we have i ≤ δ. By Eq. ( 6), we also have i ↑S ≤ δ ↑S . Moreover, we know that δ ↑S ⊇ x ↑S ∪ y ↑S because δ = (x ↑S ∪ y ↑S ). This implies that we have δ ↑S ≤ δ, and so i ↑S ≤ δ.

In addition, by Eq. ( 5), we get that i ≤ i ↑S , which means that, for all join-irreducible elements i ∈ δ ↓ ∨ I(P ) , we have i ≤ i ↑S ≤ δ. Therefore, combined with the fact that δ ↓ ∨ I(P ) = δ, we finally obtain that δ ↓ι(S) = δ. In plain English, this means that δ is equal to the join of all the iota elements of S that are less than δ. So, by definition of L S , we get that δ ∈ L S . Thus, the meet of two iota elements

ι 1 ∧ ι 2 , where ι 1 , ι 2 ∈ ι(S), is in L S .
It only remains to consider the meet of two arbitrary elements of L S , i.e. x ∧ y, where x, y ∈ L S . Notice that if x = S or y = S, then x ∧ y = S ∈ L S . Otherwise, it can be decomposed as follows:

x ∧ y = x ↓ι(S) ∧ y ↓ι(S)

Since P follows the distributive law Eq. ( 3), we can rewrite this equation as:

x ∧ y = ι1∈x ↓ι(S) ι2∈y ↓ι(S)

(ι 1 ∧ ι 2 )
The meet of two iota elements of S being in L S , we get that x ∧ y is equal to the join of elements that are all in L S . As we already established that L S is an upper-subsemilattice of P , we get that the meet of two arbitrary elements of L S is also in L S . Thus, L S is a lower-subsemilattice of P as well and therefore a sublattice of P .

In addition, notice that for all element s ∈ S and for all i ∈ s ↓ ∨ I(P ) , we have by construction i ≤ i ↑S ≤ s. Therefore, P being a lattice, we have s = s ↓ ∨ I(P ) = s ↓ι(S) , i.e. s ∈ L S . Besides, if P ∈ S, then it is equal to S, which is also in L S by construction. So, S ⊆ L S . It follows that the meet or join of every nonempty subset of S is in L S , i.e. M S ⊆ L S and J S ⊆ L S , where M S is the smallest meet-closed subset of P containing S and J S is the smallest join-closed subset of P containing S. Furthermore, iota elements are defined as the meet of a set of elements of S, which implies that they are necessarily all contained in M S , i.e. ι(S) ⊆ M S . This means that we cannot build a smaller sublattice of P containing S. Therefore, L S is the smallest sublattice of P containing S.

Finally, let us verify that all iota elements are join-irreducible elements of L S . For any join-irreducible element i ∈ ∨ I(P ), assume there are two distinct elements x, y ∈ L S such that x < i ↑S and y < i ↑S . This implies by Eq. ( 6) and ( 7) that x ↑S ≤ i ↑S and y ↑S ≤ i ↑S . Moreover, if i ≤ x and i ≤ y, then by Eq. ( 6), we get that i ↑S ≤ x ↑S and i ↑S ≤ y ↑S , which means that x = y = i ↑S . This contradicts the fact that x = y. Thus, we get that i ≤ x and i ≤ y. Lemma 3.1.1, this implies that i ≤ x ∨ y. Since i ≤ i ↑S , we have necessarily x ∨ y = i ↑S and so x ∨ y < i ↑S . Therefore, i ↑S is a join-irreducible element of L S , i.e. ι(S) is the set containing only the join-irreducible elements of L S .

A.2 Theorem 3.2.1

Proof. Consider the sequence (H k ) k∈ 1,n , where H k = (L, E k ) and:

E k = (x, y) ∈ L 2 / y = x ∨ i n+1-k .
By definition, for all k ∈ 1, n and ∀(x, y) ∈ E k , we have x, y ∈ L and x ≤ y, i.e. (x, y) ∈ E ≤ . Reciprocally, every arrow e ∈ E ≤ can be decomposed as a unique path (e 1 , e 2 , . . . , e

n ) ∈ A 1 × A 2 × • • • × A n , where A k = E k ∪ I P :
Similarly to the FMT, this sequence builds unique paths simply by generating the whole lattice L step by step with each join-irreducible element of L. However, unlike the FMT, the join-irreducible elements of L are not necessarily atoms. Doing so, pairs of join-irreducible elements may be ordered, causing the sequence to skip or double some elements. And even if all the join-irreducible elements of L are atoms, since L is not necessarily a Boolean lattice, the join of two atoms may be greater than a third atom (e.g. if L is the diamond lattice), leading to the same issue. Indeed, it is easy to build a path between two elements x, y of L such that x ≤ y: At step 1, we take the arrow (x, x ∨ i n ) if i n ≤ y (we take the identity arrow (x, x) otherwise). At step 2, we take the arrow (p, p ∨ i n-1 ) if i n-1 ≤ y, where p = x ∨ i n or p = x depending on whether or not i n ≤ y, and so on until we get to y. Obviously, we cannot get to y if we take an arrow (p, p ∨ i) where i ≤ y. So, any path from x to y only consists of arrows obtained with join-irreducible elements that are less than y. But, are they all necessary to reach y from x? Let i k be a join-irreducible element such that i k ≤ y. This join-irreducible element is only considered in E n+1-k . Suppose we do not take the arrow at step n + 1k, i.e. we replace it by an identity arrow (p, p), where p was reached through a path from x with arrows at steps 1 to nk. Since L is a distributive lattice, and since its join-irreducible elements are ordered such that ∀i j , i l ∈ ∨ I(L), j < l ⇒ i j ≥ i l , we have by Corollary 3.1.1 that for any k ∈ 1, n , i k ≤ ∨ I(L) k-1 . So, if i k ≤ p, then by Lemma 3.1.1, we also have i k ≤ p ∨ ∨ I(L) k-1 . Since ∨ I(L) k-1 contains all join-irreducible elements considered after step n + 1k, this implies that there is no path from p to an element greater than i k . Yet, i k ≤ y. Thus, if i k ≤ p, then y can only be reached from p through a path containing the arrow (p, p ∨ i k ). Otherwise, if i k ≤ p, then p = p ∨ i k , which means that only an identity arrow can be taken at step n + 1k anyway. Either way, there is only one arrow that can be taken at step n + 1k to build a path between p and y. All join-irreducible elements less than y must be used to build a path from x to y. Thereby, this path is unique, meaning that Theorem 2.3.1 is satisfied. The sequence (H k ) k∈ 1,n computes the same zeta transformations as G < .

A.3 Theorem 3.2.2

Proof. Consider the sequence (H k k∈ 1,n , where H k = (M, E k ) and:

E k = (x, y) ∈ M 2 / x = (y ∨ i k ) ↑M and x ≤ y ∨ ι(M ) k ,
where ι(M

) k = {i 1 , i 2 , . . . , i k }.
By definition, for all k ∈ 1, n and ∀(x, y) ∈ E k , we have x, y ∈ M and x ≥ y, i.e. (x, y) ∈ E ≥ . Reciprocally, every arrow e ∈ E ≥ can be decomposed as a unique path (e 1 , e 2 , . . . , e

n ) ∈ A 1 × A 2 × • • • × A n , where A k = E k ∪ I P :
Recall the procedure, described in Theorem 3.2.1, that builds unique simply by generating all elements of a finite distributive lattice L ⊇ M , based on the join of its join-irreducible elements, step by step. Here, the idea is to do the same, except that we remove all elements that are not in M . Doing so, the only difference is that the join y ∨ i k of an element y ∈ M with a join-irreducible element i k ∈ ι(M ) of this hypothetical lattice L may not be in M . However, thanks to the meet-closure of M , we can "jump the gap" between two elements y and p of M , should they be separated by elements of L\M . Indeed, for all join-irreducible element i k ∈ ι(M ), if x ≥ y ∨ i k , then since M is meet-closed and x ∈ M , there is a unique element p ∈ M that we call proxy such that p = (y ∨ i k ) ↑M . In complement, the synchronizing condition p ≤ y ∨ ι(M ) k ensures the unicity of this jump, and so the unicity of the path between any two elements x and y of M . Finding a path from x to y is easy: take all iota elements less than x, and simply compute successive joins with them, starting from y. At step n, we take the arrow ( (y ∨ i n ) ↑M , y) if i n ≤ x, and (y, y) otherwise. At step n -1, we take the arrow ( (p ∨ i n-1 ) ↑M , p) if i n-1 ≤ x, where p = (y ∨ i n ) ↑M or p = y, depending on whether or not i n ≤ x. Proceeding as such until x is reached guarantees the existence of a path, since the synchronizing condition is always satisfied. Then, the question is: Are there other paths? Obviously, for some p ∈ M such that x ≥ p, no path from x to y can contain arrows ( (p ∨ i) ↑M , p) if i ≤ x. Thus, it contains only arrows corresponding to joins with iota elements that are less than x. Next, let us consider some element p ∈ M . If i k-1 ≤ p, then p = (p ∨ i k-1 ) ↑M , which means that only an identity arrow (p, p) can be taken at step k -1. Otherwise, if i k-1 ≤ p, then the arrow ( (p ∨ i k-1 ) ↑M , p) can only exist in the sequence if (p ∨ i k-1 ) ↑M ≤ p ∨ ι(M ) k-1 . We know by Corollary 3.1.1 that i k ≤ ι(M ) k-1 . By Lemma 3.1.1, this implies that if i k ≤ p, then i k ≤ p∨ ι(M ) k-1 , which means that i k ≤ (p∨i k-1 ) ↑M . Through the same reasoning, this means that i k ≤ (p ∨ i k-1 ) ↑M ∨ i k-2 ↑M . In fact, by recurrence, we have

i k ≤ • • • (p ∨ i k-1 ) ↑M ∨ i k-2 ↑M • • • ∨ i 1 ↑M
. Thus, if i k ≤ p, then no element greater than i k can be at the tail of a path leading to p through arrows of the sequence. This means that on a path from x to y, if i k ≤ x, then at step k, either i k ≤ p (i.e. we can only take the identity arrow (p, p)) or i k ≤ p, which implies that we must take the arrow ( (p ∨ i k ) ↑M , p). This implies that all iota elements less than x must be used in the joins corresponding to the arrows of the path from x to y. Therefore, the path described above is unique, which satisfies Theorem 2.3.1. The sequence (H k ) k∈ 1,n computes the same zeta transformations as G > .

B Implementation of the Efficient Möbius Transformations (EMT)

We present in this section evidence-based algorithms for the computation of DST transformations such as the commonality function q and the implicability function b, as well as their inversions, namely the mass function m and the conjunctive and disjunctive weight functions w and v. All these algorithms have better complexities than the FMT, i.e. less than O(|Ω|.2 |Ω| ).

We implemented these algorithms as a general-purpose C++ evidence-based framework along with combination rules from DST. We plan to transpose this implementation as a Python package in the near future to ease its usage. Code and implementation details can be found at [START_REF] Chaveroche | evidence-based-DST[END_REF].

B.1 Data structure

B.1.1 Overview

The core of our implementation uses the class bitset (a contiguous sequence of bits) from the standard C++ library, along with a special dynamic binary tree of our design presented in section B.1.3. This tree allows us to search for supersets or subsets without having to consider all sets. For simple look-ups, i.e. just to get the value associated with a set, we use Hashmaps, since they feature constant time complexities for look-up and insertion.

Each representation of evidence (mass function, commonality function, implicability function, conjunctive weight function, disjunctive weight functions, etc) has its own class. A mass function is an object containing a tree of values different from 0, i.e. corresponding to focal sets. It inherits the abstract class mobius transform which simply defines the behavior of storing values such as focal sets. An object inheriting this abstract class can be created either directly, by providing a key-value object such as an Hashmap or a tree, or indirectly, through inversion of a given zeta transform and a given order relation (⊆ or ⊇). It also features methods to remove negligeable values and renormalize. The conjunctive and disjunctive weight functions also inherit this abstract class. For these last classes, all set that is not present in their tree is associated with 1.

Other representations inherit the abstract class zeta transform. This abstract class defines the behavior of computing focal points from focal sets, given some order relation, and storing their values. It also keeps its mobius transform object in memory for eventual additional projections, i.e. to get the value associated with other sets than focal points. An object inheriting this abstract class can be created either directly, by providing another zeta transform object, or indirectly, by providing an object inheriting the mobius transform abstract class, an order relation (⊆ or ⊇) and an operation (+ or ×). For the latter, you may also provide a specific computation scheme (without structure, as a semilattice or as a lattice). This class also features methods to find the value associated with a non-focal point. The commonality, implicability and plausibility functions inherit this abstract class.

B.1.2 Frame of discernment

A frame of discernment (FOD), noted Ω, is represented as an object containing an array of labels and a Hashmap that enables one to find the index associated with a particular label.

B.1.3 Powerset function

Our data structure for powerset functions (i.e. functions that assign values to elements of 2 Ω ) is based on the representation of sets as binary strings, as in [START_REF] Wilson | Algorithms for Dempster-Shafer Theory[END_REF] and [START_REF] Haenni | Implementing belief function computations[END_REF], and on the binary tree depicted in Fig. 11. It is a dynamic powerset binary tree, only storing nodes corresponding to special sets. All other set not present in the tree is assumed to be associated with a fixed value (i.e. 0 for a mass function, 1 for a weight function). Thus, special sets include focal sets but may not all be focal sets, as is the case with the lattice support. Each node in the tree contains a boolean value to indicate whether it has been set to a value or not, an eventual value, pointers to parent and children, its depth index and a bitset representing an element from 2 Ω . 11 with an analogous data structure proposed by Wilson [START_REF] Wilson | Algorithms for Dempster-Shafer Theory[END_REF]. It is a binary tree in which values are only assigned to terminal leaves, not intermediate nodes. As in Fig. 11, for the sake of clarity, the structure is shown as if it was static, where all elements from 2 Ω are considered special elements.

The creation of this tree is incremental, starting with the singleton {ω 1 }, where Ω = [ω 1 , . . . , ω n ], as root, whether it is a special set or not. The next special set is inserted to its right or left given that it contains ω 1 or not. In fact, for a pair (A, value), where A is a special set, this procedure will assign value to a node of depth equal to the greatest index in 1, n corresponding to an element of A. This node is found following the binary code that represents A to navigate the tree until the last element index is encountered in A, i.e. until we reach the last bit set to 1 in A. So, for some other special set B, if B contains all elements of A, in addition to other ones including one of greater maximum index, then B is inserted at the right of A. If B has all elements of A, in addition to other ones not including one greater than the maximum index of A, then B is not on the same branch as A and will be assigned to a node of same depth as A. All supersets of A have a depth equal to or greater than its. Of course, this also means that all subsets of A have a depth equal to or less than its. Moreover, sets that are at the left of A are not contained in A and do not contain A, since they have all elements of A but the one of greatest index, in addition to others of greater index than the maximum index of A. Furthermore, if B diverges with A before its depth, it may be necessary to create a disjunction. A disjunction node (i.e. a node that does not hold any value) is inserted to split the branch in two at the depth equal to the first element index not common to both A and B. The one that does not contain it will be placed at the left of this disjunction node, and the one that does will be placed at its right. This behavior is illustrated in Fig. 12.

A similar binary tree for powerset functions has been proposed in [START_REF] Wilson | Algorithms for Dempster-Shafer Theory[END_REF]. It is illustrated in Fig. 13. While both our binary tree and theirs are dynamic, theirs does not exploit depths and requires to store 2F -1 elements, where F is the number of special elements to store. Ours needs to store at most F + F 2 elements, and only F if every disjunction node between two special sets is also a special set (or if there is simply no disjunction between special sets, e.g. in the consonant case). Furthermore, it features interesting properties like the fact that the search for all singletons and some sub-FODs can be restrained respectiveley to the left and right chains of nodes. As mentioned above, having depths allows us to exploit the fact that subsets can only be of lower depth, while supersets can only be of greater depth. This form of powerset binary tree also speeds up the search for any value since we have to check at most n booleans to find a value, where n ∈ [1, |Ω|], while the version of [START_REF] Wilson | Algorithms for Dempster-Shafer Theory[END_REF] always have to check n booleans.

for i = 1 to |S| do for ii = i + 1 to |F | do A ← F [ii] • S[i]; if A ∈ F Map .keys() then append A to F ; F Map [A] ← 0;
Recently, another similar structure to ours has been proposed in [START_REF] Polpitiya | A Framework for efficient computation of belief theoretic operations[END_REF][START_REF]Efficient Computation of Belief Theoretic Conditionals[END_REF]. However, their data structure is not dynamic, i.e. it stores all subsets instead of only special sets. Doing so, they do not have to store a binary string in each node, but they always have an overall exponential spatial complexity (and of course, a time complexity at least exponential accordingly).

In the case of an infinite FOD, the idea is to represent it as an ever changing FOD containing a special element ω ∞ as first element that symbolizes the rest of the FOD. As we know that ω ∞ will always be an element of this FOD, having {ω ∞ } as the root node of its powerset binary tree reduces the number of operations of reorganization after addition or removal of any FOD element.

B.2 Procedures computing focal points

In this section, we present algorithms computing all focal points, given focal sets.

B.2.1 General procedure

Here, we apply Property 2 of section 3.4 of [START_REF] Chaveroche | Focal points and their implications for möbius transforms and dempster-shafer theory[END_REF] to the case where P = 2 Ω , leading to Algorithm 1. For a set S ⊆ 2 Ω , e.g. supp(f ), this algorithm computes its focal points o S, where o ∈ {∧, ∨} with a complexity less than O(|S| . | o S|) in time and O(| o S|) in space.

B.2.2 Linear analysis

There are some cases in which a linear pre-analysis of complexity O(|S|) both in time and space is sufficient to find all focal points. This analysis focuses on the progressive union of all focal sets in a linear run. Formally, let S\{Ω} = {A 1 , A 2 , . . . , A K } and S\{Ω} k = {A 1 , A 2 , . . . , A k }. This analysis focuses on I i = U i-1 ∩ A i such that i ∈ 2, K , and U i-1 = S\{Ω} i-1 and I 1 = A 1 . More precisely, we have

I i = U i-1 ∩ A i = ( S\{Ω} i-1 ) ∩ A i = F ∈{A1,...,Ai-1} (F ∩ A i ) .
In other words, these intersections I i contain all focal points based on pairs of focal sets.

In most cases, without testing each pair of focal sets, we cannot know which focal points are generated based solely on I i since several combinations of sets in 2 Ii can lead to I i as union. For example, if Ω = {a, b, c, d} and S\{Ω} = {{a, b}, {a, c}, {b, c, d}}, then U 2 = {a, b, c} and I 3 = {a, b, c} ∩ {b, c, d} = {b, c}. Yet, {b, c} is not a focal point. It is the result of the union of the focal points {a, b} ∩ {b, c, d} = {b} and {a, c} ∩ {b, c, d} = {c}.

However, there are two special cases in which we know that

I i is a focal point: (a) if |I i | = 0, then 2 Ii = {I i }, and (b) if |I i | = 1, then 2 Ii = {I i , ∅}. So, if ∀i ∈ 2, K , |I i | = 0, then ∀F 1 , F 2 ∈ S\{Ω}, F 1 ∩ F 2 = ∅.
This is the quasi-Bayesian case that has already been treated in Proposition 1 of [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF]. By definition of this case, we have ∀F ∈ S\{∅, Ω}, F ↑ ∧ S = {Ω} and the only possible focal point other than the focal sets is ∅, i.e. ∧ S\{∅} = S\{∅}. This means that for any powerset function f such that supp(f ) ⊆ S, the computation of its zeta and Möbius transforms in

(2 Ω , ⊇) is always O(|supp(f )|), where |supp(f )| ≤ |Ω| + 2.
In addition, this analysis points to a slightly more general case that contains the quasi-Bayesian one in which ∀i ∈ 2, K , |I i | ≤ 1. Indeed, when |I i | = 1, we have 2 Ii = {I i , ∅}, which means that all focal points composing I i are in {I i , ∅} and at least one of them is the singleton I i , since ∅ is the neutral element for the union of sets. Also, the only new focal point that could be generated based on the intersection of the singleton I i with another focal point is ∅.

Algorithm 2 sums up this procedure for ∧ S. This linear analysis can be performed for the dual order ⊆ as well, focusing on S\{∅} = {A 1 , A 2 , . . . , A K }, with I i = U i-1 ∪ A i such that i ∈ 2, K , and U i-1 = S\{∅} i-1 and I 1 = A 1 . This dual procedure is provided by Algorithm 3.

B.3 Computation of iota elements

B.7 Computation of DST transformations in a lattice

The general procedure to compute o S is less than O(|S|.| o S|). But, if one wishes to be certain that our algorithms are at least as efficient as the FMT, i. Algorithms 25 to 32 present procedures using L S (more precisely, the upper and lower closures S ↑ L S and S ↓ L S ) to compute the following transformations:

• m to b, • b to m,
• m to q,

• q to m,

• b to v,
• v to b,

• q to w,

• w to q. They all use the sequences of graphs of Theorem 3. • m to q,

• q to m,

• b to v,
• v to b,

• q to w,

• w to q. Fig. 14 offers a decision tree to help the reader in choosing the right algorithm for their case. Of course, this decision tree can be implemented as an algorithm in order to create a unique general procedure automatically choosing the type of algorithm to use, no matter the DST transformation. q(F K ) ← m(F K ); for i = K -1 to 1 do q(F i ) ← m(F i ) + q(F i+1 ); m(F K ) ← q(F K ); for i = K -1 to 1 do m(F i ) ← q(F i )q(F i+1 ); w(F K ) ← q(F K ) -1 ; for i = K -1 to 1 do w(F i ) ← q(F i ) -1 . q(F i+1 ); q(F K ) ← w(F K ) -1 ; for i = K -1 to 1 do q(F i ) ← w(F i ) -1 . q(F i+1 );

Example 2 . 1 . 1 .Example 2 . 1 . 2 .

 211212 In DST, the implicability function b is defined as the zeta transform of the mass function m in (2 Ω , ⊆), i.e.: ∀B ∈ 2 Ω , b(B) = A⊆B m(A) In DST, the implicability function b is also the inverse of the multiplicative zeta transform of the disjunctive weight function v in (2 Ω , ⊆), i.e.: ∀B ∈ 2 Ω , b(B) = A⊆B v(A) -1

Figure 1 :

 1 Figure 1: Illustration representing the paths generated by the arrows contained in the sequence (Hi) i∈ 1,3 , where Hi = (2 Ω , Ei) and Ei = {(X, Y ) ∈ 2 Ω × 2 Ω / Y = X ∪ {ωi}} and Ω = {a, b, c}. This sequence computes the same zeta transformations as G⊂ = (2 Ω , E⊂), where E⊂= {(X, Y ) ∈ 2 Ω × 2 Ω / X ⊂ Y }.A dot represents the node of its column. Its row i corresponds to both the tail of a potential arrow in Hi and the head of a potential arrow in Hi-1. The last row corresponds to the heads of all potential arrows that could be in H3. The arrows represents the actual arrows in each graph Hi. Identity arrows are ignored in computations and not displayed here for the sake of clarity. If they were, there would be vertical arrows in every column, linking each dot in row i to the next dot of same node in row i + 1. This representation is derived from the one used in[START_REF] Kennes | Computational aspects of the Mobius transformation of graphs[END_REF].

Figure 2 :

 2 Figure 2: Illustration representing the paths generated by the arrows contained in the sequence (Hi) i∈ 1,3 , where Hi = (2 Ω , Ei) and Ei = {(X, Y ) ∈ 2 Ω × 2 Ω / X = Y ∪ {ωi}} and Ω = {a, b, c}. This sequence computes the same zeta transformations as G⊃ = (2 Ω , E⊃), where E⊃ = {(X, Y ) ∈ 2 Ω × 2 Ω / X ⊃ Y }.

Example 3 . 1 . 2 .

 312 Taking back Example 3.1.1, the ordering required in this Corollary 3.1.2 simply translates to sorting the meet-irreducible elements of L from the largest set to the smallest set. Thus, sorting ∧

Figure 4 :

 4 Figure 4: Illustration representing the paths generated by the arrows contained in the sequence (H k ) k∈ 1,4 , where H k = (L, E k ) and E k = {(X, Y ) ∈ L 2 / Y = X ∪ i k } and L = {∅, {a}, {d}, {a, d}, {c, d, f }, {a, c, d, f }, Ω} and Ω = {a, b, c, d, e, f } and (i k ) k∈ 1,4 = ({a}, {d}, {c, d, f }, Ω). This sequence computes the same Möbius transformations as G⊂ = (L, E⊂), where E⊂ = {(X, Y ) ∈ L 2 / X ⊂ Y }. The "-1" labels emphasize the intended use of the operatorwith this sequence.

Figure 5 :

 5 Figure 5: Illustration representing the paths generated by the arrows contained in the sequence (H k ) k∈ 1,4, whereH k = (L, E k ) and E k = {(X, Y ) ∈ L 2 / X = Y ∪ i k } and L = {∅,{a}, {d}, {a, d}, {c, d, f }, {a, c, d, f }, Ω} and Ω = {a, b, c, d, e, f } and (i k ) k∈ 1,4 = ({a}, {d}, {c, d, f }, Ω). This sequence computes the same zeta transformations as G⊃ = (L, E⊃), where E⊃ = {(X, Y ) ∈ L 2 / X ⊃ Y }.

  Figure 5: Illustration representing the paths generated by the arrows contained in the sequence (H k ) k∈ 1,4, whereH k = (L, E k ) and E k = {(X, Y ) ∈ L 2 / X = Y ∪ i k } and L = {∅,{a}, {d}, {a, d}, {c, d, f }, {a, c, d, f }, Ω} and Ω = {a, b, c, d, e, f } and (i k ) k∈ 1,4 = ({a}, {d}, {c, d, f }, Ω). This sequence computes the same zeta transformations as G⊃ = (L, E⊃), where E⊃ = {(X, Y ) ∈ L 2 / X ⊃ Y }.

Figure 6 :

 6 Figure 6: Illustration representing the paths generated by the arrows contained in the sequence (H k ) k∈ 1,4 , whereH k = (L, E k ) and E k = {(X, Y ) ∈ L 2 / X = Y ∪ i 5-k } and L = {∅, {a}, {d}, {a, d}, {c, d, f }, {a, c, d, f }, Ω} and Ω = {a, b, c, d, e, f } and (i k ) k∈ 1,4 = ({a}, {d},{c, d, f }, Ω). This sequence computes the same Möbius transformations as G⊃ = (L, E⊃), where E⊃ = {(X, Y ) ∈ L 2 / X ⊃ Y }. The "-1" labels emphasize the intended use of the operatorwith this sequence.

  This sequence is illustrated in Fig. 7. The execution of any transformation based on this sequence is at most O(|ι(M )|.|M |) in space and O(|ι(M )|.|M |.ǫ) in time, where ǫ represents the average number of operations required to "bridge a gap", i.e. to find the minimum of (y ∨ i k ) ↑M . Proof. See Appendix A.3

4. 1

 1 General usageIf |supp(f )| is of same order of magnitude as | ∨ I(P )| or lower, then we can directly compute the focal points ∧ supp(f ) or ∨ supp(f ). Next, with ∧ supp(f ), we can compute Efficient Möbius Transformations based on Theorem 3.2.2 to get the zeta or Möbius transform of any function f in (P, ≥).

Example 4 . 1 . 1 .

 411 Consider the mass function m and the commonality function q from Example 2.1.3. The transformation ((H k ) k∈ 1,n , m, +), where ∧ supp(f ) = ∧ supp(m), computes the commonality function q.

∅

  {a,e,f} {c,d,e,f}{a,c,d,e,f} {a,b,c,e,f} {a,b,d,e,f} {b,c,d,e,f}

  i2, . . . , i k } and J = {∅, {a, e, f }, {c, d, e, f }, {a, c, d, e, f }, {a, b, c, e, f }, {a, b, d, e, f }, {b, c, d, e, f }, Ω} and Ω = {a, b, c, d, e, f } and (i k ) k∈ 1,5 = ({b

Example 4 . 1 . 2 .

 412 Consider the mass function m and the commonality function q from Example 2.2.3. The transformation ((H n+1-k ) k∈ 1,n , q, -), where ∧ supp(f ) = ∧ supp(m), computes the mass function m.

Example 4 . 1 . 3 .

 413 Consider the conjunctive weight function w and the commonality function q from Example 2.1.4. The transformation ((H k ) k∈ 1,n , w -1 , ×), where ∧ supp(f ) = ∧ supp(w -1), computes the commonality function q. Example 4.1.4. Consider the conjunctive weight function w and the commonality function q from Example 2.2.4. The transformation ((H n+1-k ) k∈ 1,n , w -1 , /), where ∧ supp(f ) = ∧ supp(w -1), computes the conjunctive weight function w.

Example 4 . 1 . 5 .Example 4 . 1 . 6 .Example 4 . 1 . 7 .

 415416417 Consider the mass function m and the implicability function b from Example 2.1.1. The transformation ((H k ) k∈ 1,n , m, +), where ∨ supp(f ) = ∨ supp(m), computes the implicability function b. Consider the mass function m and the implicability function b from Example 2.2.1. The transformation ((H n+1-k ) k∈ 1,n , b, -), where ∨ supp(f ) = ∨ supp(m), computes the mass function m. Consider the disjunctive weight function v and the implicability function b from Example 2.1.2. The transformation ((H k ) k∈ 1,n , v -1 , ×), where ∨ supp(f ) = ∨ supp(v -1), computes the implicability function b.

∅

  {a,e,f} {c,d,e,f}{a,c,d,e,f} {a,b,c,e,f} {a,b,d,e,f} {b,c,d,e,f}

Example 4 . 1 . 8 .

 418 Consider the disjunctive weight function v and the implicability function b from Example 2.2.2. The transformation ((H n+1-k ) k∈ 1,n , v -1 , /), where ∨ supp(f ) = ∨ supp(v -1), computes the disjunctive weight function v. These transformations can be computed in at most O(| ∨ I(P )|.|supp(f )|+|I(supp(f ))|.| o supp(f )|) operations, where I ∈ {ι, ι} and o ∈ {∧, ∨}, which is at most O(| ∨ I(P )|.|P |). Otherwise, if |supp(f )| ≫ | ∨ I(P )|, then we can compute supp(f ) ↑ L supp(f ) or supp(f ) ↓ L supp(f ) from the lattice support of Proposition 3.1.3, and then compute Efficient Möbius Transformations based on Theorem 3.2.1. Doing so, computing the same transforms can be done in at most O(| ∨ I(P )|.|supp(f )| + |I(supp(f ))|.|supp(f ) A L supp(f ) |) operations, where I ∈ {ι, ι} and A ∈ {↑, ↓}, which is at most O(| ∨ I(P )|.|P |). Either way, it is always possible to compute zeta and Möbius transforms in a distributive lattice in less than O(| ∨ I(P )|.|P |) in time and space.

4. 2

 2 Dempster-Shafer Theory So, we can always compute most DST transformations (See Examples 4.1.1 to 4.1.8), wherever the FMT applies, in less than O(|Ω|.2 |Ω| ) operations in the general case. The EMT are always more efficient than the FMT.

Figure 11 :Figure 12 :

 1112 Figure11: Illustration depicting our data structure for powerset functions on the frame of discernment Ω = {a, b, c}. It is a binary tree with values on nodes and leaves. For the sake of clarity, the structure is shown as if it was static, where all elements from 2 Ω are considered special elements. We see clearly that it reproduces the natural generation of the powerset lattice, encapsulating the powerset of every {ω 1 , . . . , ωn} in the powerset of {ω 1 , . . . , ω n+1 }. As a consequence, the search for all singletons and all these sub-FODs can be restrained respectiveley to the left and right chain of nodes.

Figure 13 :

 13 Figure 13: Same example as in Fig.11with an analogous data structure proposed by Wilson[START_REF] Wilson | Algorithms for Dempster-Shafer Theory[END_REF]. It is a binary tree in which values are only assigned to terminal leaves, not intermediate nodes. As in Fig.11, for the sake of clarity, the structure is shown as if it was static, where all elements from 2 Ω are considered special elements.

  Computation of the iota elements (See Proposition 3.1.1) and dual iota elements (See Proposition 3.1.2) of S are presented respectively in Algorithms 4 and 5.B.4 Computation of the lattice supportComputation of the upper and lower closure in the lattice support of S (See Proposition 3.1.3) are presented respectively in Algorithms 6 and 7.

  e. at most O(|Ω|.2 |Ω| ), then one has to look at |S|. Indeed, if O(|S|) ≤ O(|Ω|) (e.g. |S| < 10.|Ω|), then O(|S|.| o S|) ≤ O(|Ω|.2 |Ω| ). Otherwise, one can rely on the lattice support L S, since ι(S) can be computed in less than O(|Ω|.|S|) with Algorithm 4 and is then used to compute o S in O(ι(S).| L S|) in Algorithms 6 and 7, where |ι(S)| ≤ |Ω|.

  2.1 and its corollaries. Their complexity in time is less than O(I(S).| L S|), where I ∈ {ι, ι} and o ∈ {∧, ∨}, which is always less than O(|Ω|.2 |Ω| ). Their space complexity is less than O(| L S|). B.8 Computation of DST transformations independently from Ω If supp(f ) is almost Bayesian or if |Ω| happens to be considerable to the point that one would like to compute the previous DST transformations independently from |Ω|, Algorithms 33 to 40 present procedures of time complexities in [O(| o S|), O(| o S| 2 )]. Their complexity in space is O(| o S|). They present procedures for the following transformations: • m to b, • b to m,

Algorithm 9 : 5 OFigure 14 :

 9514 Figure 14: Decision tree for the choice of which algorithms of section B to use. Of course, this decision tree can be implemented as an algorithm in order to create a unique general procedure automatically choosing the type of algorithm to use, no matter the DST transformation. Diamond nodes represent Boolean tests. Rectangle nodes represent the chosen action. Finally, terminal nodes (leaves) indicate the final time complexity of the whole procedure, including the computation of any DST transformation, where o ∈ {∧, ∨} and I ∈ {ι, ι}. In particular, when is almost Bayesian is true, the complexity of the whole procedure is O(S). Notice that all these complexities are less than O(|Ω|.2 |Ω| ).

Algorithm 10 :Algorithm 11 :

 1011 Computation of {m(B) / B ∈ S } based on {b(B) / B ∈ S } in the consonant case.Input:{b(B) / B ∈ S }, is consonant, S = {F 1 , F 2 , . . . , F K }, where |F 1 | ≤ |F 2 | ≤ • • • ≤ |F K | Output: {m(B) / B ∈ S } if is consonant then m(F 1 ) ← b(F 1 ); for i = 2 to K do m(F i ) ← b(F i )b(F i-1 ); Computation of {q(B) / B ∈ S } based on {m(B) / B ∈ S } in the consonant case. Input: {m(B) / B ∈ S }, is consonant, S = {F 1 , F 2 , . . . , F K }, where |F 1 | ≤ |F 2 | ≤ • • • ≤ |F K | Output: {q(B) / B ∈ S } if is consonant then

Algorithm 12 :

 12 Computation of {m(B) / B ∈ S } based on {q(B) / B ∈ S } in the consonant case.Input: {q(B) / B ∈ S }, is consonant, S = {F 1 , F 2 , . . . , F K }, where|F 1 | ≤ |F 2 | ≤ • • • ≤ |F K | Output: {m(B) / B ∈ S } if is consonant then

Algorithm 13 :Algorithm 14 :Algorithm 15 :

 131415 Computation of {v(B) / B ∈ S } based on {b(B) / B ∈ S } in the consonant case.Input:{b(B) / B ∈ S }, is consonant, S = {F 1 , F 2 , . . . , F K }, where |F 1 | ≤ |F 2 | ≤ • • • ≤ |F K | Output: {v(B) / B ∈ S } if is consonant then v(F 1 ) ← b(F 1 ) -1 ; for i = 2 to K do v(F i ) ← b(F i ) -1 . b(F i-1 ); Computation of {b(B) / B ∈ S } based on {v(B) / B ∈ S } in the consonant case. Input: {v(B) / B ∈ S }, is consonant, S = {F 1 , F 2 , . . . , F K }, where |F 1 | ≤ |F 2 | ≤ • • • ≤ |F K | Output: {b(B) / B ∈ S } if is consonant then b(F 1 ) ← v(F 1 ) -1 ; for i = 2 to K do b(F i ) ← v(F i ) -1 . b(F i-1 ); Computation of {w(B) / B ∈ S } based on {q(B) / B ∈ S } in the consonant case. Input: {q(B) / B ∈ S }, is consonant, S = {F 1 , F 2 , . . . , F K }, where |F 1 | ≤ |F 2 | ≤ • • • ≤ |F K | Output: {w(B) / B ∈ S } if is consonant then

Algorithm 16 :

 16 Computation of {q(B) / B ∈ S } based on {w(B) / B ∈ S } in the consonant case.Input:{w(B) / B ∈ S }, is consonant, S = {F 1 , F 2 , . . . , F K }, where |F 1 | ≤ |F 2 | ≤ • • • ≤ |F K | Output: {q(B) / B ∈ S } if is consonant then

Algorithm 34 :

 34 Computation of {m(B) / B ∈ ∨ S} based on {b(B) / B ∈ ∨ S } independently from |Ω|.Input: {b(B) / B ∈ ∨ S } Output: {m(B) / B ∈ ∨ S } sort ∨ S such that ∨ S = {A 1 , A 2 , . . . , A K }, where |A 1 | ≤ |A 2 | ≤ • • • ≤ |A K |; for i = 1 to K do m(A i ) ← b(A i ); foreach B ∈ ∨ S / B ⊂ A i do m(A i ) ← m(A i )m(B); Algorithm 35: Computation of {q(B) / B ∈ ∧ S } based on {m(B) / B ∈ S } independently from |Ω|. Input: {m(F ) / F ∈ S } Output: {q(B) / B ∈ ∧ S } foreach B ∈ ∧ S do q(B) ← m(B); foreach F ∈ S / F ⊃ B do q(B) ← q(B) + m(F );Algorithm 36: Computation of {m(B) / B ∈ ∧ S} based on {q(B) / B ∈ ∧ S } independently from |Ω|.Input: {q(B) / B ∈ ∧ S } Output: {m(B) / B ∈ ∧ S } sort ∧ S such that ∧ S = {A 1 , A 2 , . . . , A K }, where |A 1 | ≤ |A 2 | ≤ • • • ≤ |A K |; for i = K to 1 do m(A i ) ← q(A i ); foreach B ∈ ∧ S / B ⊃ A i do m(A i ) ← m(A i )m(B); Algorithm 37: Computation of {v(B) / B ∈ ∨ S } based on {b(B) / B ∈ ∨ S } independently from |Ω|. Input: {b(B) / B ∈ ∨ S }, ∨ S Output: {w(B) / B ∈ ∨ S } sort ∨ S such that ∨ S = {A 1 , A 2 , . . . , A K }, where |A 1 | ≤ |A 2 | ≤ • • • ≤ |A K |; for i = 1 to K do v(A i ) ← b(A i ) -1 ; foreach B ∈ ∨ S / B ⊂ A i do v(A i ) ← v(A i )/v(B);

  These two sequences of graphs are the foundation of the Fast Möbius Transform (FMT) algorithms. Their execution is O(n.2 n ) in time and O(2 n ) in space. As we can see, the FMT presented here proposes two transformations ((H i ) i∈ 1,n , f, +) that computes the same

	∅	{a}	{b}	{a, b}	{c}	{a, c} {b, c}	Ω

  This sequence is illustrated in Fig. 3. The execution of any transformation based on this sequence is O(n.|L|) in time and O(|L|) in space. It can be shown similarly that the sequence (H k ) k∈ 1,n computes the same zeta transforms as the sequence of Theorem 3.2.1, where H k = (L, E k ) and:

	Proof. See Appendix A.2.
	Corollary 3.2.1.

  in reverse order compared to the join-irreducible elements of Theorem 3.2.1.

Corollary 3.2.2. Consider the sequence (H k ) k∈ 1,n , where H k = (L, E k ) and:

  in reverse order compared to the join-irreducible elements of Corollary 3.2.2. Corollary 3.2.4. Dually, consider the sequence (H k ) k∈ 1,n , where H k = (L, E k ) and:

Algorithm 1 :

 1 Computation of the focal points associated with (S, ≤), where ≤ ∈ {⊆ , ⊇}.

	Input: S, ≤
	Output: F , F Map
	F ← S;
	F Map ← Hashmap<bitset, float>;
	for i = 1 to |S| do
	F Map [S[i]] ← 0;
	if ≤ = ⊆ then
	// | is the bitwise OR operator
	• ← |;
	else
	// & is the bitwise AND operator
	• ← &;

The following definitions hold for lower semifinite partially ordered sets as well, i.e. partially ordered sets such that the number of elements of P lower in the sense of ≤ than another element of P is finite. But for the sake of simplicity, we will only talk of finite partially ordered sets.

⋆ This work was carried out and co-funded in the framework of the Labex MS2T and the Hauts-de-France region of France. It was supported by the French Government, through the program "Investments for the future" managed by the National Agency for Research (Reference ANR-11-IDEX-0004-02).

Algorithm 2: Linear computation of ∧ S based on S.

Input: S\{Ω} = {A

if included then append i to I;

Algorithm 6: Computation of S ↑ L S based on ι(S) and S.

B.5 Computation of DST transformations in the consonant case

The consonant case has already been treated in Proposition 2 of [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF]. A consonant structure of evidence is a nested structure where each focal set is contained in every focal set of greater or equal cardinality. Formally,

Their complexity in time is min [O(|Ω|), O (|S|. log (|S|))] (which corresponds to the complexity of the sorting algorithm used on S). Their space complexity is O(|S|).

Algorithm 8: Consonance check.

Input: S Output: is consonant sort S such that S = {F 1 , F 2 , . . . , F K }, where

B.6 Computation of DST transformations in a semilattice

Algorithms 17 to 24 present procedures using ∧ S or ∨ S to compute the following transformations:

• m to q,

• q to m,

• v to b,

• q to w,

• w to q.

They all use the sequences of graphs of Theorem 3.2.2 and Corollary 3.2.7. Their complexity in time is O(I(S).| o S|.ǫ), where I ∈ {ι, ι} and o ∈ {∧, ∨} and where ǫ represents the average number of operations required to "bridge a gap" (See Theorem 3.2.2). This is always less than

;

;

;

Algorithm 24: Computation of {q(B) / B ∈ ∧ S } based on {w(B) / B ∈ ∧ S }.

foreach A ∈ S ↑ L S do m(A) ← q(A);

Algorithm 29: Computation of {v(B) / B ∈ S ↓ L S } based on {b(B) / B ∈ S ↓ L S }.

Algorithm 30: Computation of {b(B) / B ∈ S ↓ L S } based on {v(B) / B ∈ S ↓ L S }. Input: {w(B) / B ∈ ∧ S }, ∧ S Output: {q(B) / B ∈ ∧ S } foreach B ∈ ∧ S do q(B) ← w(B) -1 ; foreach A ∈ ∧ S / A ⊃ B do q(B) ← q(B)/w(A);