%06/11/05
%\documentclass[11pt]{article}
\documentclass{article}
\usepackage{icecs2005}

%\usepackage[english]{babel}

\usepackage{amsmath}
\usepackage{amsfonts}
%\usepackage{multicol}
%\usepackage{vaucanson}
%\usepackage{stmaryrd}


% \parindent=0pt
% \textwidth=16cm
% \hoffset=-1.5cm


% Fontes

\font\twelvesym=msbm10 at 12pt
\font\tensym=msbm10
\font\sevensym=msbm7
\font\fivesym=msbm5

\newfam\symfam
\textfont\symfam=\tensym
\scriptfont\symfam=\sevensym
\scriptscriptfont\symfam=\fivesym
\def\sym{\fam\symfam\tensym}
\def\fns{\footnotesize}

% Sauts

\def\ss{\smallskip}
\def\ms{\medskip}
\def\mhs{\hbox to 1cm{}}
\def\bs{\bigskip}
\def\hs{\hbox to 3mm{}}
\def\hhs{\hspace{1cm}}

% Marqueurs discursifs
\newtheorem{definition}{Definition}
\newtheorem{def_prop}{Definition/Proposition}
\newtheorem{proposition}[def_prop]{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{example}{Example}
\newtheorem{conjecture}{conjecture}
\newtheorem{note}[example]{Note}

%\setcounter{section}{-1}
\def\mref#1{(\ref{#1})}
\def\Proof{\noindent {\bf Proof.} }
\def\cqfd{\par \nopagebreak\rightline{\vrule height 3pt width 5pt depth 2pt} 
\medbreak}

% Signes

\def\Box{\fbox{\hspace{2mm}}}
\def\kd#1#2{\delta{#1#2}}
\def\ncp#1#2{#1\langle #2\rangle}
\def\ncs#1#2{#1\langle\langle #2\rangle\rangle}
\def\rncs#1#2{#1\langle\langle #2\rangle\rangle^{\rm rat}}
\def\pncs#1#2{#1\langle\langle #2\rangle\rangle_{\Phi-finite}}
\def\pointir{\unskip . --- \ignorespaces}
\def\ra{\rightarrow}
\def\tl{\triangleleft}
\def\tr{\triangleright}
\def\scal#1#2{\leftangle #1| #2\rightangle}
\def\bu{$\bullet\ $}
\def\supp{\textrm{supp}}
\newcommand{\ostar}{\framebox(6.5,6.5){$*$}}


% Expressions

\def\aci{\sim_{aci}}
\def\acm#1{\sim_{acm#1}}
\def\rat{\sim_{rat}}
\def\acs{\sim_{acs}}
\def\PB#1{{\rm B}$#1$}
\def\PB{{\rm B}\ }
\def\base#1{{\mathcal B}#1}


% Lettres

\def\al{\alpha}
\def\be{\beta}
\def\ep{\epsilon}
\def\ga{\gamma}
\def\om{\omega}
\def\la{\lambda}
\def\Si{\Sigma}
\def\E{{\mathcal E}}
\def\T{{\cal T}}

% Autres lettres

\def\E{{\mathcal E}}
\def\F{{\mathcal F}}

% Constantes
\def\B{{\sym B}}
\def\N{{\sym N}}
\def\Z{{\sym Z}}
\def\Q{{\sym Q}}
\def\R{{\sym R}}
\def\C{{\sym C}}

% Operateurs

\def\scal#1#2{\langle #1 | #2 \rangle}
\def\kd#1#2{\delta{#1#2}}
\def\red{\mathbf{red}}

\title{{\bf  Rewriting Tables and Memorized Semirings}}

\name{G\'erard H.E. Duchamp$^{(1)}$, Khalaf Khatatneh$^{(2)}$, Cyrille Bertelle$^{(3)}$}
\address{
$^{(1)}$Institut Galil\'ee - University of Paris XIII - 99, avenue Jean-Baptiste Cl\'ement,  
\\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
}

% \author{
% Cyrille Bertelle
% \footnote{LIH, Laboratoire d'Informatique du Havre, 
% 25 rue Philippe Lebon, 
% BP 540 
% 76058 Le Havre cedex, France
% },\\
% G\'erard H. E. Duchamp
% \footnote{LIPN, 
% Institut Galil\'ee - Universit\'e Paris XIII
% 99, avenue Jean-Baptiste Cl\'ement,  
% 93430 Villetaneuse, France}\\ and\\ 
% Khalaf Khatatneh\footnote{LIFAR, Facult\'e des Sciences et des Techniques,
% 76821 Mont-Saint-Aignan Cedex, France}
% \thanks{\tt cyrille.bertelle@univ-lehavre.fr, gerard.duchamp@lipn.univ-paris13.fr, 
% khalaf.khatatneh@univ-rouen.fr}}

%\date{}
\begin{document}
\maketitle

%\begin{multicols}{2}

\ss
{\bf Keywords:} Tables, $k$-subsets, efficient data structures, efficient algebraic structures.

\section{INTRODUCTION}
The following is intended to be a contribution in the area of what could be called 
{\it efficient algebraic structures}  or {\it 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 \cite{G1}.

Reduced tables realize the (finite) $k$-sets sets of Eilenberg \cite{Ei}, 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 {\it 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.


\section{DESCRIPTION OF THE DATA STRUCTURE}

\subsection{Tables}\label{table}

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,+,\times)$ and for which matrix computation remains valid, say the structure of a semiring \cite{G1}.

A table $T$ is a two-rows array, the first row being filled with monomials (upper row) taken in some given semigroup 
(see \cite{DHL}, \cite{LA} or \cite{Lo}).
This is equivalent to saying that a Table is a finite {\it multiset} of columns.

Multisets are extensively used in rewriting theory and sometimes named {\it bags}. A multiset $M={s_1,s_2,\cdots}$ is a set in which elements are 
allowed to be repeated which amounts to the data of a mapping $f : Dom(f)\mapsto \N^+$, $Dom(f)$ is the {\it 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 {\it indices} of the table ($I(T)$) and for the second row  ($V(T)$) the 
{\it values} or ({\it 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$.

\section{Description of the data structure}

\subsection{Tables}\label{table}

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,+\infty[$ including 
\begin{enumerate}
\item $+$ (ordinary sum)
\item $\times$ (ordinary product)
\item min (if over $[0,1]$, with neutral $1$, otherwise must be extended to $[0,+\infty]$ and then, with neutral $+\infty$) or max
\item $+_a$ defined by $x+_a y:=log_a(a^x+a^y)$ ($a>0$)
\item $+_{[n]}$ (H\"older laws) defined by $x+_{[n]} y:=\sqrt[n]{x^n+y^n}$ 
\item $+^s$ (shifted sum, $x+^c y:=x+y-1$, over whole $\R$, with neutral $1$)
\item $\times^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)
\end{enumerate}

\ss
For other examples and applications see, for example \cite{G1}.\\
A table $T$ is a two-rows array, the first row being filled with monomials taken in a given semigroup $S$ (see \cite{DHL}, \cite{LA} or \cite{Lo}).
To be more precise, if 

\begin{center}
$T=$
\begin{tabular}{c|c|c|c}
$u_1$ 	& 	$u_2$ 	& $\cdots $ & $u_k$\\
\hline
$p_1$ 	& 	$p_2$ 	& $\cdots $ & $p_k$\\
\end{tabular}
\end{center}

individual columns are allowed to be repeated that is, for instance that one can get
\begin{center}
\begin{tabular}{c|c|c|c|c}
$\cdots$ &	$u_i$ & $\cdots$ & $u_i$ & $\cdots$\\
\hline
$\cdots$ & 	$p_i$ & $\cdots $ & $p_i$ & $\cdots$\\
\end{tabular}
\end{center}

and columns commute between themselves, that is 

\begin{center}
\begin{tabular}{c|c|c|c|c}
$\cdots$ &	$u_i$ & $\cdots$ & $u_j$ & $\cdots$\\
\hline
$\cdots$ & 	$p_i$ & $\cdots $ & $p_j$ & $\cdots$\\
\end{tabular}
\qquad
$=$
\qquad
\begin{tabular}{c|c|c|c|c}
$\cdots$ &	$u_j$ & $\cdots$ & $u_i$ & $\cdots$\\
\hline
$\cdots$ & 	$p_j$ & $\cdots $ & $p_i$ & $\cdots$\\
\end{tabular}
\end{center}

This is equivalent to saying that a Table is a finite {\it multiset} of columns.\\
Multisets \cite{mw1} are extensively used in rewriting theory and sometimes named {\it bags}. A multiset $M={s_1,s_2,\cdots}$ is a set in which elements are 
allowed to be repeated which amounts to the data of a mapping $f : Dom(f)\mapsto \N^+$, $Dom(f)$ is the {\it 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 {\it indices} of the table ($I(T)$) and for the second row the 
{\it values} or ({\it 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$.



\subsection{The reduction system $\red$}\label{table}

\subsubsection{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=$
\begin{tabular}{|c|}
$u_i$\\
\hline
$p_i$\\
\end{tabular}
$i=1,2$ with the same index $u_1=u_2=u$, we define the reduction 
\begin{equation*}
T\stackrel{\red}{\longrightarrow} T-\{c_1,c_2\}+c_3
\end{equation*}  
where 
$c_3=$
\begin{tabular}{|c|}
$u$\\
\hline
$p_1+p_2$\\
\end{tabular}

\begin{def_prop} 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\stackrel{\red^*}{\longrightarrow} T_1
$$
will be denoted $\red(T)$.
\end{def_prop}


\subsubsection{Operations on tables}\label{table}

Let us consider, two tables $T_1,\ T_2$ and a commutative and associative law $*$ over the coefficients. 
One has the proposition
\begin{proposition} i) The reduction of $T_3:=T_1\uplus T_2$ 
(multiset union) depends only on the reduction of $T_i;\ i=1,2$.\\
ii) More precisely set
\begin{center}
$R_1=\red(T_1)=$
\begin{tabular}{c|c|c|c}
$u_1$ 	& 	$u_2$ 	& $\cdots $ & $u_k$\\
\hline
$p_1$ 	& 	$p_2$ 	& $\cdots $ & $p_k$\\
\end{tabular}
\\
\vspace*{0.4cm}%\hs 
and
\vspace*{0.4cm}%\hs 
\\
$R_2=\red(T_2)=$
\begin{tabular}{c|c|c|c}
$v_1$ 	& 	$v_2$ 	& $\cdots $ & $v_l$\\
\hline
$q_1$ 	& 	$q_2$ 	& $\cdots $ & $q_l$\\
\end{tabular}
\end{center}

then $\red(T_1\uplus T_2)=R_1\ostar_p R_2=R_3$ where  $R_3[w]=T_i[w]$ if $w\in I(T_i)$ and $w\notin I(T_{3-i})$
and by $R_3[w]=T_1[w]* T_2[w]$ if $w\in I(T_1)\cap I(T_2)$

\ss
In particular one has $I(R_1\ostar_p R_2)=I(R_1)\cup I(R_2)$.
\end{proposition}

\begin{note}
i) At this stage one do no need any neutral. The structure automatically creates it (the emty table, see {\rm algebraic remarks} below for full 
explanation).\\
ii) The above is a considerable generalization of an idea appearing in \cite{CD}, aimed only to semirings with units.
\end{note}

For convolution type, one needs two laws over $k$, say $\oplus, \otimes$, the second being distributive over the first, i.e. identically 
\begin{eqnarray}
x\otimes (y\oplus z)&=&(x\otimes y)\oplus (x\otimes z)\ \mathrm{and}\cr
(y\oplus z)\otimes x&=&(y\otimes x)\oplus (z\otimes x) 
\end{eqnarray}

Taking into account that a table is, in a unique way a (commutative) sum of columns it is sufficient to define $\otimes$ for two columns, 
which reads
\begin{equation}
\begin{tabular}{|c|}
$u_1$\\
\hline
$p_1$\\
\end{tabular}
\ \bigotimes_c\ 
\begin{tabular}{|c|}
$u_2$\\
\hline
$p_2$\\
\end{tabular}
\ :=\ 
\begin{tabular}{|c|}
$u_1u_2$\\
\hline
$p_1\times p_2$\\
\end{tabular}
\end{equation}


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. 

\begin{proposition} 
Let $T_i, i=1;2$\\ 
i) The reduction of $T_3:=T_1\otimes T_2$ 
depends only on the reduction of $T_i;\ i=1,2$.\\
ii) More precisely set
\begin{center}

$R_1=\red(T_1)=$
\begin{tabular}{c|c|c|c}
$u_1$ 	& 	$u_2$ 	& $\cdots $ & $u_k$\\
\hline
$p_1$ 	& 	$p_2$ 	& $\cdots $ & $p_k$\\
\end{tabular}
\\
\vspace*{0.4cm}%\hs 
and
\vspace*{0.4cm}%\hs 
\\
$R_2=\red(T_2)=$
\begin{tabular}{c|c|c|c}
$v_1$ 	& 	$v_2$ 	& $\cdots $ & $v_l$\\
\hline
$q_1$ 	& 	$q_2$ 	& $\cdots $ & $q_l$\\
\end{tabular}
\end{center}

then there exists a (unique) law $\otimes_p$ on the reduced tables such that 

\begin{equation}
\red(T_1\otimes T_2)=R_1\otimes_c R_2=R_3
\end{equation}

iii) The space of tables with coefficients in $k$ and monomials in $S$, $\T(K,S)(\uplus,\otimes_c)$ is a semiring with additive neutral 
(the empty table). Moreover, this semiring has multiplicative unit if $S$ is a monoid.
\end{proposition}

\subsection{Total mass}

The total mass of a table is just the sum of the coefficients in the bottom row. One can check that 
\begin{eqnarray}
mass(T1\oplus T2)&=&mass(T1)+mass(T2);\cr
mass(T1\otimes T2)&=&mass(T1) \cdot  mass(T2)
\end{eqnarray}
this allows, if needed, stochastic conditions.

\subsection{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. {\it Magmas} and {\it Semirings}. For formal 
definitions, see

{\small{\tt http://\\
encyclopedia.thefreedictionary.com/\\
Magma\%20category}

\ss
{\tt http://mathworld.wolfram.com/\\
Semiring.html}}\\


\begin{proposition} (i) Let $(S,*)$ be a magma, $\Si$ an alphabet, and denote $T[S]$ the set of tables with indices in $\Si^*$ and values in $S$. 
Define $\ostar_p$ as in \mref{table}. Then\\
i) The law $\ostar$ is associative (resp. commutative) iff $*$ is. 
Moreover the magma $(\T[S],\ostar)$ always possesses a neutral, the empty table (i.e. with an empty set  of indices).\\
ii) If $(K,\oplus,\otimes)$ is a semiring, then $(\T_K,\oplus,\otimes)$ is a semiring.\\
\end{proposition}

\Proof (Sketch) Let $S_{(1)}$ the magma with unit built over $(S\cup \{e\})$ by adjunction of a unit. Then, to each table $T$, associate the (finite 
supported) function $f_T: \Sigma^*\mapsto S_{(1)}$ defined by
\begin{equation}
f_T(w) = 
\left\{ 
\begin{array}{lll} 
  T[w] & \mbox{if $w\in I(T)$}\\
   e & \mbox{otherwise} 
\end{array}
\right.
\end{equation}
then, check that $f_{T_1\ostar_p T_2}=f_{T_1}\ostar_1 f_{T_2}$ (where $\ostar_1$ is the standard law on $S_{(1)}^{(\Sigma^*)}$) and that the 
correspondence is a isomorphism. Use a similar technique for the point (ii) with $K_{0,1}$ the semiring with units constructed over $K$ and show 
that the correspondence is one-to-one and has $K_{0,1}\langle \Sigma \rangle$ as image.

\begin{note} 1) Replacing $\Sigma^*$ by a simple set, the (i) of proposition above can be extended without modification (see also $K$-subsets in 
\cite{Ei}).\\
2) If one replaces the elements of free monoid on the top row by elements of a semigroup $S$ and admits some colums with a top empty 
cell, we get the algebra of $S_{(1)}$.\\ 
3) Pointwise product can be considered as being constructed with respect to the (Hadamard) coproduct $c(w)=w\otimes w$ whereas convolution 
is w.r.t. the Cauchy coproduct
\begin{equation}
c(w)=\sum_{uv=w}u\otimes v
\end{equation}  
(see \cite{DFLL}).
\end{note}


\section{APPLICATIONS}
\subsection{Specializations and images}

{\bf Multiplicities, Stochastic and Boolean}

Whatever the multiplicities, one gets the classical automata by emptying the alphabet (setting $\Sigma =\emptyset$). 

{\bf 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 \cite{Ka}).

Let $\T$ be here the table semiring with coefficients in $([0,+\infty],min,+)$. Then a table 
\begin{equation}
T=
\begin{tabular}{c|c|c|c|c}
$u_1$ 	& $\cdots$ &	$u_k$ 	& $\cdots $ & $u_n$\\
\hline
$l_1$ 	& $\cdots$ &	$l_k$ 	& $\cdots $ & $l_n$\\
\end{tabular}
\end{equation}
can be written so that $l_1=\cdots=l_k<l_{m}$ for $m>k$ (this amounts to say that the set where the minimum is reached is 
$\{u_1,u_2\cdots u_k\}$). Then, to such a table, one can associate $\phi(T):=[\{u_1,u_2\cdots u_k\},l_1]$ in the memorized semiring. 
It is easy to check that $\phi$ transports the laws and the neutrals and obtain the result.

\subsection{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. 
%we can apply to automata with mutations (see \cite{B1,B2}).
They give operational tools for modelling agent behaviour for various simulations in the domain of distributed artificial intelligence \cite{B2}.
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 ours 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 \cite{B1}.
Thus, tables and memorized semiring are promizing tools for this kind of implementation which leads to model complex systems in many domains.   


%\begin{thebibliography}{ABC}
\begin{thebibliography}{IEEEbib}

%
\bibitem{B1} Bertelle C., Flouret M., Jay V., Olivier D., Ponty J.-L., {\it Genetic Algorithms on Automata with Multiplicities for Adaptative 
Agent Behaviour in Emergent Organisations}.
%
\bibitem{B2} Bertelle C., Flouret M., Jay V., Olivier D., Ponty J.-L., {\it Automata with Multiplicities as Behaviour Model in Multi-Agent 
Simulations} SCI 2001.
%
\bibitem{CD} Champarnaud J.-M., Duchamp G., {\it Derivatives of rational expressions\\ and related theorems}, 
T.C.S. {\bf 313} 31 (2004).
%
\bibitem{DHL} Duchamp G., Hatem Hadj Kacem, \'Eric Laugerotte, {\it On the erasure  of  several letter-transitions}, 
JICCSE'04
%
\bibitem{DFLL} Duchamp G., Flouret M., Laugerotte E., Luque J-G., {\it Direct and dual laws for automata with 
multiplicites}, Theoret. Comput. Sci. 267 (2001) 105-120.
%
\bibitem{Ei} Eilenberg S., {\it Automata, languages and machines, Vol A}, Acad. Press (1974).
%
\bibitem{G1} {\sc Golan, J. S.}, {\it Power algebras over semirings with applications in Mathematics 
and Computer Science}, Kluwer (1999).
%
\bibitem{LA} Laugerotte E., Abbad H., {\it Symbolic computation on weighted automata}, JICCSE'04.
%
\bibitem{Lo} Lothaire M., {\it Combinatorics on words}, Cambridge University Press (new edition), 1997.
%
\bibitem{Ka} Khatatneh K., {\it Construction of a memorized semiring}, DEA ITA Memoir, University of Rouen (2003).
%
\bibitem{mw1} {\tt http://mathworld.wolfram.com\\
/Multiset.html}
\end{thebibliography}

%\end{multicols}
\end{document}