Dioid Algebra

Introduction

Dioid algebra is a powerful mathematical tool that allows a linear description of some systems that would have a very non-linear representation if described by differential or difference equations. In particular, Discrete Event Dynamic Systems (DEDS) where synchronization phenomena predominate.

DEDS are systems whose state transitions are triggered by events that occur at discrete instants. For example, the number of packets inside a communication network and the number of pieces in a manufacturing system are state variables that change at events like “arrival” or “departure” of items (packets or pieces). DEDS are often associated to technological systems like computer systems, flexible manufacturing systems, telecommunication networks, traffic control systems, multiprocessor operating systems and logistic systems.

There are specific techniques to represent DEDS. For examples, see [1-2].

Dioids: Definition

A dioid is a set D endowed with two closed operations called “addition” (⊕) and “multiplication” (⊗). The usual notation is D = (D, ⊕, ⊗). The operations of a dioid must satisfy the following axioms, ∀a,b,c ∈ D :

• Commutativity of addition: a ⊕ b = b ⊕ a
• Associativity of addition: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
• Associativity of multiplication: (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c)
• Distributivity of multiplication over finite sums: (a ⊕ b) ⊗ c = (a ⊗ c) ⊕ (b ⊗ c) and
  c ⊗ (a ⊕ b) = (c ⊗ a) ⊕ (c ⊗ b)
• Existence of a null element: ∃ε ∈ D : ε ⊕ a = a ⊕ ε = a
• Absortion by the null element: ε ⊗ a = a ⊗ ε = ε
• Existence of an unity element: ∃e ∈ D : e ⊗ a = a ⊗ e = a
• Idempotency of addition: a ⊕ a = a

The majority of the axioms that define a dioid are, thus, common to the “normal” algebra of real numbers. The two really big differences are:

1. Idempotency of addition;

2. Absence of a symmetric element (like -a).

For these characteristics, dioids are also called idempotent semi-rings.

Dioids: Examples

Possibilities of functions that can define a sum in a dioid include minimization (min), maximization (max), union (∪) and the logic OR.

Example 1 (Max-Plus dioid): Consider R_±∞ = R ∪ {-∞} ∪ {+∞}. Given a,b ∈ R_±∞, define:

R_max = (R_±∞,⊕,⊗) is a dioid. In R_max: ε = -∞, e = 0 and

Example 2: Consider R_+∞ = R⁺ ∪ {+∞} (just non-negative real numbers are considered). Given a,b ∈ R_+∞, define:

R = (R_+∞,⊕,⊗) is also a dioid. In R: ε = +∞, e = 0 and

Dioids: Other Examples

Some other examples of dioids are presented in Table 1.

Note that these structures satisfy the idempotency of addition.

Dioids: Classification

Dioids can be classified according to their characteristics. For example:

• Commutative dioids: dioids with commutative multiplications, i.e.,
  ∀a,b ∈ D: ab = ba.

  Most of the time, the symbol ⊗ is omitted as it is the case in the conventional algebra. Also as usual, a^k, k ∈ N, denotes the product a ⊗ … ⊗ a (k times)
  and a⁰ = e.

• Complete dioids: dioids that are closed for infinite sums, and the distributivity applies for infinite sums.
• Subdioid: subset D_s of dioid D = (D,⊕,⊗) that satisfy
  • ε ∈ D_s and e ∈ D_s;
  • D_s is closed for ⊕ and ⊗.
• Entire dioids: A dioid that satisfy
  ab = ε ⇒ a = ε or b = ε.

Diod R_max of Example 1 and dioid R of example Example 2 are complete commutative dioids.

Order in Dioids

A partial order in a dioid can be defined by the following equivalency, ∀a,b ∈ D:

This equivalency defines a partial order, because two elements of a dioid are not always comparable. There can exist elements a,b such that a ⊕ b = c, with c ≠ a and c ≠ b.

In the recent literature of dioids, it is common to use the symbol instead of ≤ and the symbol instead of ≥. In this section, we use symbols ≤ and ≥ to denote order in diods and symbols ≤_R and ≥_R to denote order in the conventional sense.

Notice that the order between two elements of a dioid depends on the definition of sum. For example, for the Max-Plus dioid in Example 1:  2 ≤ 3.5 , but for the dioid in Example 2:  2 ≥ 3.5 .

Define T in a dioid D = (D,⊕,⊗) as the sum of all elements in D. From the definition of order in dioids, T is the maximum element of D (or top element). For the dioid of Example 1,

and for the dioid of Example 2,

Let a,b ∈ D be two elements of a complete dioid D. Define a ∧ b ∈ D as the least upper bound between a and b, i.e., the greatest element of D that is smaller than or equal to a and b. Then:

Residuated Functions and Residuals

Consider the following problem in a given dioid:

• Determine the values of x that satisfy the equation f(x) = b, as a function of b.

As it happens in the usual algebra of real numbers, this problem can have multiple solutions or can have no solutions at all. In dioids, in general, it is solved a relaxation of this problem given by

• Find the maximum solution of  f(x) ≤ b;
• Find the minimum solution of  f(x) ≥ b.

The first problem is addressed by the residuation and the second (or dual) problem is addressed by the dual residuation, as defined next.

Let f: A → B be an isotone mapping from a complete dioid A into a complete dioid B. If ∀b ∈ B the set of solutions of f(x) ≤ b is non-empty and has a maximum element, denoted f ^#(b) (unique), then f is called a residuated function and f ^#(b) is called the residual of f at b.

Similarly, if ∀b ∈ B the set of solutions of f(x) ≥ b is non-empty and has a minimum element, denoted f ^b(b) (unique), then f is said dual-residuated and f ^b(b) is the dual-residual of f at b.

Define l_a(x) = a ⊗ x and r_a(x) = x ⊗ a. For any dioid, functions l_a(x) and r_a(x) are residuated. The residual functions are denoted, respectively, l_a^#(y) = a ⊂⊃ \ y and r_a^#(y) = y ⊂⊃ / a.

Properties of Residuation

Table 2 presents some properties of the residuation operation.

∀a,b,c ∈ D:

Residuation: Example

As an example of how to determine a residuation function, it is calculated next the residual function l_a^#(y) = a ⊂⊃ \ y of function l_a(x) = a ⊗ x for the dioid of Example 2, i.e.,
R = (R_+∞ = R⁺ ∪ {+∞}, min, +).

Consider ≤_R and ≥_R the ordering symbols for the conventional algebra, i.e., given a,b ∈ R_+∞:

Residuation is related to the solutions of the inequality f(x) ≤ b. In this case, we have:

From the definition of order in dioids and the definition of sum in R,

However, as a function from R into R, the residual of l_a(x) has to be in R_+∞ = R⁺ ∪ {+∞}. Therefore, the solutions of f(x) ≤ b, in this case, must also satisfy x ≥_R 0. This implies that

Notice that as R is commutative, then

Some Notes on Dioids

Operations like +∞ - ∞ can be well defined in dioids, depending on the meaning of each term.

To guarantee that the axioms that define a dioid are satisfied for ε and T, we have:

From the definition of residuation, we also have:

Consider dioid R_max = (R ∪ {+∞} ∪ {-∞},max,+) of Example 1. We have ε = -∞, T = +∞ and
l_a^#(y) = y - a (prove it!). From the above equations, we must have:

Therefore, as -∞ and +∞ are added to the set D that define a dioid, they are treated as any other element of D, leading to well defined results, depending on the operation that is being processed.

The next sections are optional to understand most of the section
NC and Dioid Algebra.

Fixed Point Equations, mod-z Equivalence and Quotient Dioids

Define the Kleene Closure of a ∈ N as follows

Fixed Point Equations: Given a,b ∈ D (complete), the minimum solution of equation
x = ax ⊕ b is given by x = a^*b. Moreover, any solution of x = ax ⊕ b satisfies x = a^*x.

Given a,b ∈ D (complete), the maximum solution of equation x = x ⊂⊃ / a ∧ b is given by
x = b ⊂⊃ / a^*. Moreover, any solution of x = x ⊂⊃ / a ∧ b satisfies x = x ⊂⊃ / a^*.

Mod-z Equivalence: Given a,b,z ∈ D (commutative dioid), a and b are mod-z equivalent if

The notation is a ≡ b mod z.

Quotient Dioids: It is possible to properly define ⊕ and ⊗ operations between the equivalence classes defined above. The result is a new dioid called quotient dioid, denoted D/z, whose elements are classes of D. Usually, a class is represented by its greatest element.

Dioids of Formal Power Series

A formal power series with coefficients in a dioid D is a mapping f from N (or Z) into D such that ∀t ∈ N (or Z), f(t) represents the coefficient of δ^t, i.e.,

Not every term in f must be explicitly written. The missing terms have coefficient ε.

The set of formal series is endowed with the following operations:

The set of series endowed with these operations is a dioid denoted D [[δ]], with zero element ε defined by f(k) = ε_D, ∀k, and unity element e defined by f(0) = e_D, and f(k) = ε_D, otherwise (ε_D and e_D are, respectively, the zero and unit elements of dioid D).

An order in D [[δ]] is defined as follows. Given f,g ∈ D [[δ]]:

For f,h ∈ D [[δ]]:

Bibliography

1. F. Baccelli, G. Cohen, G. J. Olsder and J.-P. Quadrat. “Synchronization and Linearity: An Algebra for Discrete Event Systems,” England: John Wiley & Sons, 1992.

   
   

2. C. G. Cassandras and S. Lafortune. “Introduction to Discrete Event Systems,” Kluwer Academic Publishers, 1999.