REWRITING TABLES AND MEMORIZED SEMIRINGS

Gérard H.E. Duchamp^{(1)}, Khalaf Khatatneh^{(2)}, Cyrille Bertelle^{(3)}

(1)Institut Galilée - University of Paris XIII - 99, avenue Jean-Baptiste Clément,

93430 Villetaneuse, France.

(2) Al-Balqa’Applied University - Al-Salt, 19117, Jordan.

(3) LIH - University of Le Havre - 25 rue Ph. Lebon, BP 540, 76058 Le Havre cedex, France

Keywords: Tables, k-subsets, efficient data structures, efficient algebraic structures.

1. INTRODUCTION

The following is intended to be a contribution in the area of what could be called efficient algebraic structures or efficient data structures. In fact, we define and construct a new data structure, the tables (abstract and reduced), which are at first special multisets of two-raws arrays. The first raw is filled with words (or more generally, elements taken in some semigroup) and the second with some coefficients taken in a semiring [7].

Reduced tables realize the (finite) k-sets sets of Eilenberg [6], they are versatile (one can vary the monomials and the coefficients), easily implemented and fast computable. Varying the scalars and the transformations on them, one can obtain many different structures and, among them, semirings. Examples will be provided and worked out in full detail.

As an application, we present a new semiring (with several semiring structures) which can be applied to the necessity of automatic processing multi-agents behaviour problems. The purpose of this account/paper is to expound also the basic elements of these new structures from a combinatorial point of view. These structures show a bunch of properties. They will be endowed with several laws namely : Sum, Hadamard product, Cauchy product, Fuzzy operations (min, max, complemented product). Two groups of applications are presented.

The first group is linked to the process of “forgetting” information in the tables and then obtaining, for instance, a memorized semiring. The latter is specially suited to solve the shortest path with addresses problem using the repeated squaring algorithm on matrices with entries in this semiring.

The second, linked to multi-agent systems, is announced by showing a methodology to manage emergent organization from individual behaviour models.

2. DESCRIPTION OF THE DATA STRUCTURE

2.1. Tables

The input alphabet being set by the automaton under consideration, we will here rather focus on the definition of semirings providing transition (or transfer) coefficients. Indeed, in many applications, we have to compute the weights of paths in some weighted graph (shortest path problem, enumeration of paths, cost computations, automata, transducers to cite only a few) and the computation goes with two main rules: multiplication in series (i.e. along a path), and addition in parallel (if several paths are involved). This involves the least structure endowed with two operations (k, +, ×) and for which matrix computation remains valid, say the structure of a semiring [7].

A table T is a two-rows array, the first row being filled with monomials (upper row) taken in some given semigroup (see [4], [8] or [9]). This is equivalent to saying that a Table is a finite multiset of columns.

Multisets are extensively used in rewriting theory and sometimes named bags. A multiset M = s_{1}, s_{2}, ⋯ is a set in which elements are allowed to be repeated which amounts to the data of a mapping f : Dom(f) ↦ ℕ^{+}, Dom(f) is the support of the multiset and f the multiplicity function. If the support is finite, so is called the multiset.

The set of monomials which are present in the first row will be called the indices of the table (I(T)) and for the second row (V (T)) the values or (coefficients) of the table. The order of columns is not relevant (as in Computer Algebra Systems where this data structure is impemented).

In the sequel, we will consider two types of laws: pointwise type (subscript _{p}) and convolution type (subscript_{c}).

In order to define the pointwise and convolution composition, we must first construct one of the two central features of the paper, namely the reduction system red.

3. DESCRIPTION OF THE DATA STRUCTURE

3.1. Tables

We will first concentrate on the definition of semirings providing transition (or transfer) coefficients. For convenience, we first begin with various examples of laws on R_{+} := [0, +∞[ including

1. + (ordinary sum)

2. × (ordinary product)

3. min (if over [0, 1], with neutral 1, otherwise must be extended to [0, +∞] and then, with neutral +∞) or max

4. +_{a} defined by x +_{a} y := log_{a}(a^{x} + a^{y}) (a > 0)

5. +_{[n]} (Hölder laws) defined by x+_{[n]}y := \sqrt[n]{x^{n} + y^{n}}

6. +^{s} (shifted sum, x +^{c} y := x + y − 1, over whole R, with neutral 1)

7. ×^{c} (complemented product, x + y − xy, can be extended also to whole R, stabilizes the range of probabilities or fuzzy [0, 1] and is distributive over the shifted sum)

For other examples and applications see, for example [7]. A table T is a two-rows array, the first row being filled with monomials taken in a given semigroup S (see [4], [8] or [9]). To be more precise, if

T = \begin{matrix}u_{1} & u_{2} & ⋯ & u_{k} \\ p_{1} & p_{2} & ⋯ & p_{k} \end{matrix}

individual columns are allowed to be repeated that is, for instance that one can get

\begin{matrix}⋯ & u_{i} & ⋯ & u_{i} & ⋯ \\ ⋯ & p_{i} & ⋯ & p_{i} & ⋯ \end{matrix}

and columns commute between themselves, that is

\begin{matrix}⋯ & u_{i} & ⋯ & u_{j} & ⋯ \\ ⋯ & p_{i} & ⋯ & p_{j} & ⋯ \end{matrix} =

\begin{matrix}⋯ & u_{j} & ⋯ & u_{i} & ⋯ \\ ⋯ & p_{j} & ⋯ & p_{i} & ⋯ \end{matrix}

This is equivalent to saying that a Table is a finite multiset of columns. Multisets [11] are extensively used in rewriting theory and sometimes named bags. A multiset M = s_{1}, s_{2}, ⋯ is a set in which elements are allowed to be repeated which amounts to the data of a mapping f : Dom(f) ↦ N^{+}, Dom(f) is the support of the multiset and f the multiplicity function. If the support is finite, so is called the multiset.

The set of words which are present in the first row will be called the indices of the table (I(T)) and for the second row the values or (coefficients)of the table. The order of the columns is not relevant (as in Computer Algebra Systems where this data structure is impemented). In the sequel, we will consider two types of laws: pointwise type (subscript _{p}) and convolution type (subscript_{c}). In order to define the pointwise and convolution composition, we must first construct the one of the two central features of the paper, namely the reduction system red.

3.2. The reduction system red

3.2.1. Reduction

Let T be a table with indices in a semigroup S and values in a commutative semigroup (k, +). If T owns two

columns c_{i} = \frac{u_{i}}{p_{i}} i = 1, 2 with the same index u_{1} =

u_{2} = u, we define the reduction

T ⟶^{red} T − {c_{1}, c_{2}} + c_{3}

where c_{3} = \frac{u}{p_{1} + p_{2}}

Definition/Proposition 1 i) The reduction system defined above, denoted red, is Noetherian and Confluent. ii) The result of the complete application to the process to a table T

T ⟶^{red^{∗}} T_{1}

will be denoted red(T).

3.2.2. Operations on tables

Let us consider, two tables T_{1}, T_{2} and a commutative and associative law ∗ over the coefficients. One has the proposition

Proposition 2 i) The reduction of T_{3} := T_{1} ⊎ T_{2} (multiset union) depends only on the reduction of T_{i}; i = 1, 2. ii) More precisely set

R_{1} = red(T_{1}) = \begin{matrix}u_{1} & u_{2} & ⋯ & u_{k} \\ p_{1} & p_{2} & ⋯ & p_{k} \end{matrix}

and

R_{2} = red(T_{2}) = \begin{matrix}v_{1} & v_{2} & ⋯ & v_{l} \\ q_{1} & q_{2} & ⋯ & q_{l} \end{matrix}

then red(T_{1} ⊎ T_{2}) = R_{1}+_{p}R_{2} = R_{3} where R_{3}[w] = T_{i}[w] if w ∈ I(T_{i}) and w ∉ I(T_{3−i}) and by R_{3}[w] = T_{1}[w] ∗ T_{2}[w] if w ∈ I(T_{1}) ∩ I(T_{2})

In particular one has I(R_{1}+_{p}R_{2}) = I(R_{1}) ∪ I(R_{2}).

Note 1 i) At this stage one does not need any neutral. The structure automatically creates it (the empty table, see algebraic remarks below). ii) The above is a considerable generalization of an idea appearing in [3], aimed only to semirings with units. iii) If (k, +) possesses a neutral 0_{k}, one can add to red an extra step of withdrawing the columns with coefficient (or value) 0_{k}. The new system is Noetherian and Confluent and avoids the creation of another neutral.

For convolution type, one needs two laws over k, say ⊕, ⊗, the second being distributive over the first, i.e. identically

x ⊗ (y ⊕ z) = (x ⊗ y) ⊕ (x ⊗ z) and
(y ⊕ z) ⊗ x = (y ⊗ x) ⊕ (z ⊗ x)  (1)

Taking into account that a table is, in a unique way a (commutative) sum of columns, it is sufficient to define the convolution ⊗ for two columns, which reads

\frac{u_{1}}{p_{1}} ⨂_{c} \frac{u_{2}}{p_{2}} := \frac{u_{1}u_{2}}{p_{1} × p_{2}}  (2)

The constructed structure T (S, k) for tables is then a semiring (generally without multiplicative unit), the two laws are compatible with the reduction i.e.

Proposition 3 Let T_{i}; i = 1, 2

i) The reduction of T_{3} := T_{1} ⊗ T_{2} depends only of the reduction of T_{i}; i = 1, 2. ii) More precisely set

R_{1} = red(T_{1}) = \begin{matrix}u_{1} & u_{2} & ⋯ & u_{k} \\ p_{1} & p_{2} & ⋯ & p_{k} \end{matrix}

and

R_{2} = red(T_{2}) = \begin{matrix}v_{1} & v_{2} & ⋯ & v_{l} \\ q_{1} & q_{2} & ⋯ & q_{l} \end{matrix}

then there exists a (unique) law ⊗_{p} on the reduced tables such that

red(T_{1} ⊗ T_{2}) = R_{1} ⊗_{c} R_{2} = R_{3}  (3)

iii) The space of tables with coefficients in k and monomials in S, (T (S, k), ⊎, ⊗_{c}) is a semiring with an additive neutral (the empty table). Moreover, this semiring has a multiplicative unit if S is a monoid.

3.3. Total mass

The total mass of a table is just the sum of the coefficients in the bottom row. One can check that

mass(T 1 ⊕ T 2) = mass(T 1) + mass(T 2);
mass(T 1 ⊗ T 2) = mass(T 1) · mass(T 2) (4)

this allows, if needed, stochastic conditions.

3.4. Algebraic remarks

We have confined in this paragraph some proofs of structural properties concerning the tables. The reader may skip this section with no serious harm. First, we deal with structures with as little as possible requirements, i.e. Magmas and Semirings. For formal definitions, see

http://
encyclopedia.thefreedictionary.com/
Magma%20category
http://mathworld.wolfram.com/
Semiring.html

Proposition 4 (i) Let X be a set, (S, +) a commutative and associative semigroup. We denote T (X, S) the set of tables with indices in X and values in S and define +_{p} as in (3.2.2). Then

i) The law + is associative and commutative. Moreover the semigroup (T (X, S),+) always possesses a neutral, the empty table (i.e. with an empty set of indices). ii) If (k, ⊕, ⊗) is a semiring and X a semigroup, then the (T (X, k), ⊕, ⊗) is a semiring.

Proof. (Sketch) i) To each table T let us associate the (finite supported) function f_{T} : X ↦ S defined by

f_{T} (w) = \{ \begin{matrix}T [w] & if w ∈ I(T) \\ 0_{S} & otherwise \end{matrix}  (5)

then, check that f_{T_{1}+_{p}T_{2}} = f_{T_{1}} + f_{T_{2}} and that the correspondence T ↦ f_{T} is a isomorphism. ii) We use a similar technique to show that the correspondence T (X, k) → k[X] is one-to-one.

Note 2 Pointwise product can be considered as being constructed with respect to the (Hadamard) coproduct c(w) = w ⊗ w whereas convolution is w.r.t. the Cauchy coproduct

c(w) = ∑_{uv=w} u ⊗ v  (6)

(see [5]).

4. APPLICATIONS

4.1. Specializations and images

Multiplicities, Stochastic and Boolean

Whatever the multiplicities, one gets the classical automata by emptying the alphabet (setting Σ = ∅). Memorized Semiring

We explain here why the memorized semiring, devised at first to perform efficient computations on the shortest path problem with memory (of addresses) can be considered as an image of a ”table semiring” (thus proving without computation the central property of [10]).

Let T be here the table semiring with coefficients in ([0, +∞], min, +). Then a table

T = \begin{matrix}u_{1} & ⋯ & u_{k} & ⋯ & u_{n} \\ l_{1} & ⋯ & l_{k} & ⋯ & l_{n} \end{matrix}  (7)

can be written so that l_{1} = ⋯ = l_{k} < l_{m} for m > k (this amounts to say that the set where the minimum is reached is {u_{1}, u_{2} ⋯ u_{k}}). Then, to such a table, one can associate ϕ(T) := [{u_{1}, u_{2} ⋯ u_{k}}, l_{1}] in the memorized semiring. It is easy to check that ϕ transports the laws and the neutrals and obtain the result.

4.2. Application to evolutive systems

Tables are structured as semirings and are flexible enough to recover and amplify the structures of automata with multiplicities and transducers. They give operational tools for modelling agent behaviour for various simulations in the domain of distributed artificial intelligence [2]. The outputs of automata with multiplicities or the values of tables allow to modelize in some cases agent actions or in other cases, probabilities on possible transitions between internal states of agents behaviour. In all cases, the algebraic structures associated with automata outputs or tables values is very interesting to define automatic computations in respect with the evolution of agents behaviour during simulation.

One of our aims is to compute dynamic multiagent systems formations which emerge from a simulation. The use of table operations delivers calculable automata aggregate formation. Thus, when table values are probabilities, we are able to obtain evolutions of these aggregations as adaptive systems do.

With the definition of adapted operators coming from genetic algorithms, we are able to represent evolutive behaviors of agents and so evolutive systems [1]. Thus, tables and memorized semiring are promizing tools for this kind of implementation which leads to model complex systems in many domains.

5. REFERENCES

[1] Bertelle C., Flouret M., Jay V., Olivier D., Ponty J.-L., Genetic Algorithms on Automata with Multiplicities for Adaptative Agent Behaviour in Emergent Organisations.

[2] Bertelle C., Flouret M., Jay V., Olivier D., Ponty J.-L., Automata with Multiplicities as Behaviour Model in Multi-Agent Simulations SCI 2001.

[3] Champarnaud J.-M., Duchamp G., Derivatives of rational expressions and related theorems, T.C.S. 313 31 (2004).

[4] Duchamp G., Hatem Hadj Kacem, Éric Laugerotte, On the erasure of several lettertransitions, JICCSE’04

[5] Duchamp G., Flouret M., Laugerotte E., Luque J-G., Direct and dual laws for automata with multiplicites, Theoret. Comput. Sci. 267 (2001) 105-120.

[6] Eilenberg S., Automata, languages and machines, Vol A, Acad. Press (1974).

[7] Golan, J. S., Power algebras over semirings with applications in Mathematics and Computer Science, Kluwer (1999).

[8] Laugerotte E., Abbad H., Symbolic computation on weighted automata, JICCSE’04.

[9] Lothaire M., Combinatorics on words, Cambridge University Press (new edition), 1997.

[10] Khatatneh K., Construction of a memorized semiring, DEA ITA Memoir, University of Rouen (2003).

                                            [11] http://mathworld.wolfram.com
                                                 /Multiset.html