
\begin{Mhelppage}{WeightedAutomaton}{E.~Laugerotte}
  [ImplState=stable,TestState=alpha,DocState=stable]
%\Mproofread{...}{...}{...}

\begin{MInfo}
\eng{set of weighted automata}
\de{}
\end{MInfo}

%\begin{todo}
%\end{todo}

\begin{MIntro}
  \eng{\Mthis\Mex{(S)} creates a domain for weighted automata with 
multiplicities in the component semi-ring \Mpar{S}.}
\end{MIntro}

\begin{MDomConst}
  \MCall{S}
\end{MDomConst}

\begin{MParameters}
 \param{S}
\eng{a semiring, i.e., a domain of category Cat::SemiRing}
\de{}
\end{MParameters}

\begin{MIntro}
\eng{The domain element \Mthis\Mex{(S)(n,A,i,t,f)} represents the weighted 
automaton with multiplicities in the semi-ring $S$ 
given by its linear representation where $n$, $A$, $i$, $t$ and $f$ are 
respectively  the dimension, the alphabet, the initial vector, the transition 
function and the final vector.} 
\end{MIntro}

\begin{MDomElConst}
\MCall[\Mthis(S)]{n,A,i,t,f}
\end{MDomElConst}

\begin{MParameters}
\param{n}
\eng{positive integer.}
\de{}
\param{A}
\eng{list.}
\de{}
\param{i}
\eng{$1\times n$ sparse matrix over $S$.}
\de{}
\param{t}
\eng{table indexed by elements of $A$ whose the values are $n\times n$ sparse 
matrices over $S$.}
\de{}
\param{f}
\eng{$n\times 1$ sparse matrix over $S$.}
\de{}
\end{MParameters}

\MRelatedDomains{Dom::BooleanSemiRing, Dom::MaxMinSemiRing, 
Dom::MaxPlusSemiRing, Dom::MinMaxSemiRing, Dom::MinPlusSemiRing.}

\MMathMethods

\begin{MMethodDetails}{weight}
  \infoEng{weight of a word}
    \infoDe{}  
\call{\Mtype{dom} wa, \Mtype{DOM\_LIST} u}
\eng{The weight of the word \Mex{u} given by a list \Mex{[u1,u2,\ldots,uk]} 
is defined to be the product of sparse matrices 
\Mex{i*t[u1]*t[u2]*\ldots *t[uk]*f}.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{proper}
  \infoEng{proper automaton of a weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{The proper automaton of a weighted automaton keeps the same behaviour 
with the weight $0$ for the empty word \Mex{[]}.} 
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{addLetter}
  \infoEng{new letter and its transition matrix}
    \infoDe{}  
\call{\Mtype{dom} wa, \Mtype{any} x, \Mtype{Dom::Matrix(S)} Mx}
\eng{A letter \Mex{x} and its transition matrix \Mex{Mx} are added to the 
weighted automaton \Mex{wa}.} 
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{delLetter}
  \infoEng{removing a letter and its transition matrix}
    \infoDe{}  
\call{\Mtype{dom} wa, \Mtype{any} x}
\eng{A letter \Mex{x} and its transition matrix \Mex{Mx} is removed from the 
weighted automaton \Mex{wa}.} 
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{addState}
  \infoEng{new state with transitions, initial and final weight}
    \infoDe{}  
\call{\Mtype{dom} wa <\Mtype{Dom::Matrix(S)} it, \Mtype{Dom::Matrix(S)} ot, 
\Mtype{S} i, \Mtype{S} f>}
\eng{A state is added to the weighted automaton \Mex{wa}. It is 
indexed by \Mex{d+1} if \Mex{d} is the dimension of \Mex{wa}. If they are 
given, the ingoing transitions \Mex{it} and the outgoing transitions \Mex{ot} 
written as a row vector and a column vector respectively, are considered just 
as the initial weight \Mex{i} and the final weight \Mex{f}.} 
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{delState}
  \infoEng{delete a state}
    \infoDe{}  
\call{\Mtype{dom} wa, \Mtype{Type::PosInt} s}
\eng{The state \Mex{s} is removed from the weighted automaton \Mex{wa}.} 
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{subsTransition}
  \infoEng{insert a weight for a transition}
    \infoDe{}  
\call{\Mtype{dom} wa, \Mtype{DOM\_LIST} t <\Mtype{S} w>}
\eng{The weight \Mex{w} is put for the transition \Mex{t} in the weighted 
automaton \Mex{wa}. If it is not given, the weight is the neutral element of 
\Mex{S} for the multiplication. If the weight is the neutral element of 
\Mex{S} for the addition, the transition \Mex{t} is removed. }
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{subsInitialWeight}
  \infoEng{insert an initial weight for a state}
    \infoDe{}  
\call{\Mtype{dom} wa, \Mtype{Type::PosInt} s <\Mtype{S} w>}
\eng{The initial weight \Mex{w} is put for the state \Mex{s} in the weighted 
automaton \Mex{wa}. If it is not given, the initial weight is the neutral 
element of \Mex{S} for the multiplication. If the weight is the neutral 
element of \Mex{S} for the addition, the state \Mex{s} becomes non-initial. }
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{subsFinalWeight}
  \infoEng{insert a final weight for a state}
    \infoDe{}  
\call{\Mtype{dom} wa, \Mtype{Type::PosInt} s <\Mtype{S} w>}
\eng{The final weight \Mex{w} is put for the state \Mex{s} in the weighted 
automaton \Mex{wa}. If it is not given, the final weight is the neutral 
element of \Mex{S} for the multiplication. If the weight is the neutral 
element of \Mex{S} for the addition, the state \Mex{s} becomes non-final. }
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{automatdim}
  \infoEng{dimension of a weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{The dimension of a weighted automaton is defined to
    be the dimension of transition matrices.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{automatalph}
  \infoEng{alphabet of a weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{The alphabet of the weighted automaton is computed.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{automatinit}
  \infoEng{initial vector of a weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{The initial vector of the weighted automaton is computed.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{automattrans}
  \infoEng{transition matrix of a weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa <\Mtype{any} x>}
\eng{The transition function  of the weighted automaton is returned if 
\Mex{x} is not given, the transition matrix of \Mex{x} otherwise.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{automatfin}
  \infoEng{final vector of a weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{The final vector of the weighted automaton is computed.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{tensor}
  \infoEng{Kronecker product of sparse matrices}
    \infoDe{}  
\call{\Mtype{Dom::Matrix(S)} A,\Mtype{Dom::Matrix(S)} B}
\eng{The Kronecker product of the sparse matrices \Mex{A} and \Mex{B} is 
computed.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{mstar}
  \infoEng{Star of a sparse matrix}
    \infoDe{}  
\call{\Mtype{Dom::Matrix(S)} A}
\eng{The star of the sparse matrix \Mex{A} is computed.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{_plus}
  \infoEng{sum of weighted automata}
    \infoDe{}  
\call{\Mseq{\Mtype{dom} wa1}}
\eng{The sum \Mex{wa1+wa2+\ldots +wak} of weighted automata is defined to
    be the weighted automaton with $c1+c2+\ldots+ck$ the weight of a word $u$ 
if $ci$ is the weight of $u$ for the automaton \Mex{wai}.}
\de{}
\eng{This method overloads the function \Mup{_plus}.}
\end{MMethodDetails}

\begin{MMethodDetails}{_mult}
  \infoEng{Cauchy product of weighted automata}
\call{\Mseq{\Mtype{dom} wa1}}
\eng{The Cauchy product \Mex{wa1*wa2*\ldots *wak} of weighted automata is 
defined to be the weighted automaton with $\sum c1*c2*\ldots *ck$ the weight 
of a word $u$ if $ci$ is the weight of the word $ui$ for the automaton 
\Mex{wai} for each decomposition $u=u1u2\ldots uk$.}
\de{}
\eng{This method overloads the function \Mup{_mult}.}
\end{MMethodDetails}

\begin{MMethodDetails}{_power}
  \infoEng{Power of a weighted automaton}
\call{\Mtype{dom} wa,\Mtype{Dom::Integer} i}
\eng{The ith power \Mex{wa^i} of the weighted automaton \Mex{wa}. }
\de{}
\eng{This method overloads the function \Mup{_power}.}
\end{MMethodDetails}


\begin{MMethodDetails}{hadamard}
  \infoEng{Hadamard product of weighted automata}
    \infoDe{}  
\call{\Mtype{dom} wa1,\Mtype{dom} wa2}
\eng{The Hadamard product of two weighted automata \Mex{wa1} and \Mex{wa2} is 
defined to be the weighted automaton with $c1*c2$ the weight of 
a word $u$ if $ci$ is the weight of the word $u$ for the automaton 
\Mex{wai}.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{shuffle}
  \infoEng{shuffle product of weighted automata}
    \infoDe{}  
\call{\Mtype{dom} wa1,\Mtype{dom} wa2}
\eng{The shuffle product of two weighted automata \Mex{wa1} and \Mex{wa2} is 
computed with the shuffle of the rational noncommutative formal series $S1$ 
and $S2$ as behaviour if $S1$ and $S2$ are respectively the behaviour of 
\Mex{wa1} and \Mex{wa2}.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{infiltration}
  \infoEng{infiltration product of weighted automata}
    \infoDe{}  
\call{\Mtype{dom} wa1,\Mtype{dom} wa2}
\eng{The infiltration product of two weighted automata \Mex{wa1} and \Mex{wa2} 
is computed with the infiltration of the rational noncommutative formal series 
$S1$ and $S2$ as behaviour if $S1$ and $S2$ are respectively the behaviour of 
\Mex{wa1} and \Mex{wa2}.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{star}
  \infoEng{star of a weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{The star of a weighted automaton \Mex{wa} with the rational 
noncommutative formal series $S$ as behaviour is returned with the star of 
$S$ (if there exists) as behaviour.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{complementary}
  \infoEng{complementary of a weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{This method returns the complementary of boolean weighted automaton 
\Mex{wa}, and FAIL otherwise.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{difference}
  \infoEng{difference of weighted automata}
    \infoDe{}  
\call{\Mtype{dom} wa1,\Mtype{dom} wa2}
\eng{This method returns the difference of boolean weighted automata 
\Mex{wa1} and \Mex{wa2}, and FAIL otherwise.}
\de{}
\end{MMethodDetails}


\begin{MMethodDetails}{elimination}
  \infoEng{elimination of a letter in a weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa,\Mtype{any} x}
\eng{The x-removing of a weighted automaton \Mex{wa} produces 
(if there exists) a weighted automaton on the alphabet without x where the new 
transition matrix of a letter is computed from the product of the star of the 
transition matrix of \Mex{x} and the old transition matrix.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{isComplete}
  \infoEng{checks whether a weighted automaton is complete}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{This method returns TRUE if the weighted automaton wa is complete, and 
FALSE otherwise.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{complete}
  \infoEng{computation of the complete weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{This method returns the complete automaton corresponding to the weighted 
automaton wa.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{isAccessible}
  \infoEng{checks whether a weighted automaton is accessible}
    \infoDe{}  
\call{\Mtype{dom} wa<, \Mtype{Type::PosInt} q>}
\call{\Mtype{dom} wa<, \Mtype{Type::SetOf(Type::PosInt)} s>}
\eng{This method returns TRUE if the weighted automaton wa is 
accessible, and FALSE as well as the set of accessible states otherwise. When 
a second argument is given, if the state 
\Mex{q} (or the set \Mex{s} of states) is accessible then TRUE is returned, 
else FALSE.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{accessible}
  \infoEng{computation of the accessible weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{This method returns the accessible automaton corresponding to the 
weighted automaton \Mex{wa}.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{isCoaccessible}
  \infoEng{checks whether a weighted automaton is coaccessible}
    \infoDe{}  
\call{\Mtype{dom} wa<, \Mtype{Type::PosInt} q>}
\call{\Mtype{dom} wa<, \Mtype{Type::SetOf(Type::PosInt)} s>}
\eng{This method returns TRUE if the weighted automaton \Mex{wa} is 
coaccessible, and FALSE as well as the set of coaccessible states otherwise. 
When a second argument is given, if the 
state \Mex{q} (or the set \Mex{s} of states) is coaccessible then TRUE is 
returned, else FALSE.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{coaccessible}
  \infoEng{computation of the coaccessible weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{This method returns the coaccessible automaton corresponding to the 
weighted automaton \Mex{wa}.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{trim}
  \infoEng{computation of the trimed weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{This method returns the trimed automaton corresponding to the 
weighted automaton \Mex{wa}.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{isDeterministic}
  \infoEng{checks whether a weighted automaton is deterministic}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{This method returns TRUE if the weighted automaton wa is deterministic, 
and FALSE otherwise.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{determinization}
  \infoEng{determinization of a weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{This method returns the determinization of the weighted automaton 
\Mex{wa} if it is possible, and FAIL otherwise.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{minimization}
  \infoEng{minimization of a weighted automaton}
    \infoDe{}  
\call{\Mtype{dom} wa}
\eng{This method returns the minimization of the weighted automaton \Mex{wa} 
if it is possible, and FAIL otherwise.}
\de{}
\end{MMethodDetails}

\begin{MMethodDetails}{areEquivalent}
  \infoEng{equivalence of weighted automata}
    \infoDe{}  
\call{\Mtype{dom} wa1, \Mtype{dom} wa2}
\eng{This method checks whether the weighted automata \Mex{wa1} and \Mex{wa2} 
are the same behaviour. }
\de{}
\end{MMethodDetails}

\MConvMethods

\begin{MMethodDetails}{changeCoeffRing}
    \infoEng{conversion of a weighted automaton to a weighted automaton over 
another semiring}
\infoDe{}
\call{\Mtype{dom} wa, \Mtype{any} T}
\eng{Tries to convert the weighted automaton \Mex{wa} into a weighted 
automaton over scalars of type \Mex{T}.}
\de{}
\end{MMethodDetails}

\begin{MExample}{ex1}
\eng{We construct weighted automata with multiplicities in the MinPlus 
semiring:}
\begin{Mexin}
T:=Dom::MinPlusSemiRing:
  \end{Mexin}
  \begin{Mexin}
 W:=Dom::WeightedAutomaton(T):
  \end{Mexin}
\begin{Mexin}
TM:=Dom::Matrix(T):
  \end{Mexin}
\begin{Mexin}
alphabet1:=[a,b]: alphabet2:=[a,c]:
\end{Mexin}
\begin{Mexin}
l1:=TM(1,2,[T(2),T(infinity)]): 
\end{Mexin}
\begin{Mexin}
l2:=TM(1,3,[T(1),T(0),T(1)]): 
\end{Mexin}
\begin{Mexin}
m1[a]:=TM(2,2,[[T(0),T(1)],[T(1),T(infinity)]]):
\end{Mexin}
\begin{Mexin}
m1[b]:=TM(2,2,[[T(infinity),T(0)],[T(1),T(1)]]):
\end{Mexin}
\begin{Mexin}
m2[a]:=TM(3,3,[[T(2),T(1),T(infinity)],[T(1),T(0),T(0)],[T(1),T(infinity),
T(2)]]):
\end{Mexin}
\begin{Mexin}
m2[c]:=TM(3,3,[[T(1),T(infinity),T(0)],[T(2),T(2),T(infinity)],[T(infinity),
T(1),T(0)]]): 
\end{Mexin}
\begin{Mexin}
g1:=TM(2,1,[T(0),T(1)]):
\end{Mexin}
\begin{Mexin}
g2:=TM(3,1,[T(infinity),T(0),T(1)]):
\end{Mexin}
\begin{Mexin}
wa1:=W(2,alphabet1,l1,m1,g1);
\end{Mexin}
  \begin{Mexout}
                     +-             -+      +-             -+
+-           -+      |  0,     1     |      |  infinity, 0  |
| 2, infinity |, a = |               |, b = |               |,
+-           -+      |  1, infinity  |      |      1,    1  |
                     +-             -+      +-             -+

   +-   -+
   |  0  |
   |     |
   |  1  |
   +-   -+
  \end{Mexout}
\begin{Mexin}
wa2:=W(3,alphabet2,l2,m2,g2);
\end{Mexin}
\begin{Mexout}
                 +-                       -+
                 |  2,     1,    infinity  |
+-       -+      |                         |
| 1, 0, 1 |, a = |  1,     0,        0     |,
+-       -+      |                         |
                 |  1, infinity,     2     |
                 +-                       -+

       +-                              -+  +-          -+
       |      1,    infinity,     0     |  |  infinity  |
       |                                |  |            |
   c = |      2,        2,    infinity  |, |      0     |
       |                                |  |            |
       |  infinity,     1,        0     |  |      1     |
       +-                              -+  +-          -+
\end{Mexout}
\end{MExample}
\begin{MExample}{ex2}
\eng{The weight of a word is computed:}
\begin{Mexin}
W::weight(wa1, [a, a, b, a])
  \end{Mexin}
  \begin{Mexout}
                               3
  \end{Mexout}
\end{MExample}
\begin{MExample}{ex3}
\eng{Some functionalities  on weighted automata are presented:}
\begin{Mexin}
W::proper(wa1)
  \end{Mexin}
  \begin{Mexout}
                               +-                       -+
                               |  infinity, 2,     3     |
+-                     -+      |                         |
| 1, infinity, infinity |, a = |  infinity, 0,     1     |,
+-                     -+      |                         |
                               |  infinity, 1, infinity  |
                               +-                       -+

       +-                       -+  +-          -+
       |  infinity, infinity, 2  |  |  infinity  |
       |                         |  |            |
   b = |  infinity, infinity, 0  |, |      0     |
       |                         |  |            |
       |  infinity,     1,    1  |  |      1     |
       +-                       -+  +-          -+
\end{Mexout}
\begin{Mexin}
W::addLetter(wa1, c, TM(2, 2, [[T(2), T(1)], [T(3), T(2)]]))
  \end{Mexin}
  \begin{Mexout}
                     +-             -+      +-             -+
+-           -+      |  0,     1     |      |  infinity, 0  |
| 2, infinity |, a = |               |, b = |               |,
+-           -+      |  1, infinity  |      |      1,    1  |
                     +-             -+      +-             -+

       +-      -+  +-   -+
       |  2, 1  |  |  0  |
   c = |        |, |     |
       |  3, 2  |  |  1  |
       +-      -+  +-   -+
  \end{Mexout}
\begin{Mexin}
wa1 + wa2
  \end{Mexin}
  \begin{Mexout}
+-                    -+
| 2, infinity, 1, 0, 1 |, a =
+-                    -+

   +-                                                  -+
   |      0,        1,    infinity, infinity, infinity  |
   |                                                    |
   |      1,    infinity, infinity, infinity, infinity  |
   |                                                    |
   |  infinity, infinity,     2,        1,    infinity  |,
   |                                                    |
   |  infinity, infinity,     1,        0,        0     |
   |                                                    |
   |  infinity, infinity,     1,    infinity,     2     |
   +-                                                  -+

       +-                                                  -+
       |  infinity,     0,    infinity, infinity, infinity  |
       |                                                    |
       |      1,        1,    infinity, infinity, infinity  |
       |                                                    |
   b = |  infinity, infinity, infinity, infinity, infinity  |,
       |                                                    |
       |  infinity, infinity, infinity, infinity, infinity  |
       |                                                    |
       |  infinity, infinity, infinity, infinity, infinity  |
       +-                                                  -+

       +-                                                  -+
       |  infinity, infinity, infinity, infinity, infinity  |
       |                                                    |
       |  infinity, infinity, infinity, infinity, infinity  |
       |                                                    |
   c = |  infinity, infinity,     1,    infinity,     0     |,
       |                                                    |
       |  infinity, infinity,     2,        2,    infinity  |
       |                                                    |
       |  infinity, infinity, infinity,     1,        0     |
       +-                                                  -+

   +-          -+
   |      0     |
   |            |
   |      1     |
   |            |
   |  infinity  |
   |            |
   |      0     |
   |            |
   |      1     |
   +-          -+
  \end{Mexout}
 \begin{Mexin}
wa1*wa2
  \end{Mexin}
  \begin{Mexout}
+-                                         -+
| 2, infinity, infinity, infinity, infinity |,
+-                                         -+

       +-                                           -+
       |      0,        1,    1,     0,        0     |
       |                                             |
       |      1,    infinity, 2,     1,        1     |
       |                                             |
   a = |  infinity, infinity, 2,     1,    infinity  |,
       |                                             |
       |  infinity, infinity, 1,     0,        0     |
       |                                             |
       |  infinity, infinity, 1, infinity,     2     |
       +-                                           -+

       +-                                                  -+
       |  infinity,     0,    infinity, infinity, infinity  |
       |                                                    |
       |      1,        1,    infinity, infinity, infinity  |
       |                                                    |
   b = |  infinity, infinity, infinity, infinity, infinity  |,
       |                                                    |
       |  infinity, infinity, infinity, infinity, infinity  |
       |                                                    |
       |  infinity, infinity, infinity, infinity, infinity  |
       +-                                                  -+

       +-                                                  -+
       |  infinity, infinity,     2,        2,        1     |
       |                                                    |
       |  infinity, infinity,     3,        3,        2     |
       |                                                    |
   c = |  infinity, infinity,     1,    infinity,     0     |,
       |                                                    |
       |  infinity, infinity,     2,        2,    infinity  |
       |                                                    |
       |  infinity, infinity, infinity,     1,        0     |
       +-                                                  -+

   +-          -+
   |      0     |
   |            |
   |      1     |
   |            |
   |  infinity  |
   |            |
   |      0     |
   |            |
   |      1     |
   +-          -+
  \end{Mexout}

  \begin{Mexin}
wa1^2
  \end{Mexin}
  \begin{Mexout}
+-                               -+
| 2, infinity, infinity, infinity |,
+-                               -+

       +-                                 -+
       |      0,        1,    2,     3     |
       |                                   |
       |      1,    infinity, 3,     4     |
   a = |                                   |,
       |  infinity, infinity, 0,     1     |
       |                                   |
       |  infinity, infinity, 1, infinity  |
       +-                                 -+

       +-                                 -+  +-   -+
       |  infinity,     0,    infinity, 2  |  |  2  |
       |                                   |  |     |
       |      1,        1,    infinity, 3  |  |  3  |
   b = |                                   |, |     |
       |  infinity, infinity, infinity, 0  |  |  0  |
       |                                   |  |     |
       |  infinity, infinity,     1,    1  |  |  1  |
       +-                                 -+  +-   -+
  \end{Mexout}
\begin{Mexin}
W::hadamard(wa1, wa2)
  \end{Mexin}
  \begin{Mexout}
+-                                     -+
| 3, 2, 3, infinity, infinity, infinity |,
+-                                     -+

   a =

   +-                                                     -+
   |  2,     1,    infinity,     3,        2,    infinity  |
   |                                                       |
   |  1,     0,        0,        2,        1,        1     |
   |                                                       |
   |  1, infinity,     2,        2,    infinity,     3     |
   |                                                       |,
   |  3,     2,    infinity, infinity, infinity, infinity  |
   |                                                       |
   |  2,     1,        1,    infinity, infinity, infinity  |
   |                                                       |
   |  2, infinity,     3,    infinity, infinity, infinity  |
   +-                                                     -+

   +-          -+
   |  infinity  |
   |            |
   |      0     |
   |            |
   |      1     |
   |            |
   |  infinity  |
   |            |
   |      1     |
   |            |
   |      2     |
   +-          -+
  \end{Mexout}
\begin{Mexin}
W::shuffle(wa1, wa1)
  \end{Mexin}
  \begin{Mexout}
+-                               -+
| 4, infinity, infinity, infinity |,
+-                               -+

       +-                                        -+
       |      1,        2,        2,    infinity  |
       |                                          |
       |      2,        1,    infinity,     2     |
   a = |                                          |,
       |      2,    infinity,     1,        2     |
       |                                          |
       |  infinity,     2,        2,    infinity  |
       +-                                        -+

       +-                                        -+  +-   -+
       |  infinity,     1,        1,    infinity  |  |  0  |
       |                                          |  |     |
       |      2,        2,    infinity,     1     |  |  1  |
   b = |                                          |, |     |
       |      2,    infinity,     2,        1     |  |  1  |
       |                                          |  |     |
       |  infinity,     2,        2,        2     |  |  2  |
       +-                                        -+  +-   -+
\end{Mexout}
\begin{Mexin}
W::star(wa1)
  \end{Mexin}
  \begin{Mexout}
                               +-                -+
                               |  infinity, 2, 3  |
+-                     -+      |                  |
| 0, infinity, infinity |, a = |  infinity, 0, 1  |,
+-                     -+      |                  |
                               |  infinity, 1, 4  |
                               +-                -+

       +-                       -+  +-   -+
       |  infinity, infinity, 2  |  |  0  |
       |                         |  |     |
   b = |  infinity, infinity, 0  |, |  0  |
       |                         |  |     |
       |  infinity,     1,    1  |  |  1  |
       +-                       -+  +-   -+
\end{Mexout}
\begin{Mexin}
W::elimination(wa1, a)
  \end{Mexin}
  \begin{Mexout}
                                +-      -+  +-   -+
           +-           -+      |  2, 0  |  |  0  |
           | 2, infinity |, b = |        |, |     |
           +-           -+      |  1, 1  |  |  1  |
                                +-      -+  +-   -+
  \end{Mexout}
\end{MExample}
\begin{MExample}{ex4}
\eng{We can test if an automaton is accessible, coaccessible, or complete. 
Accessible, coaccessible, trimed or complete weighted automata can be 
computed.} 
  \begin{Mexin}
alphabet:=[a, b]:
  \end{Mexin}
  \begin{Mexin}
l:=TM(1, 2, [T(1), T(infinity)]):
  \end{Mexin}
\begin{Mexin}
m[a]:=TM(2, 2, table((1, 1) = T(1), (2, 1) = T(1))):
  \end{Mexin}
\begin{Mexin}
m[b]:=TM(2, 2, table((2, 2) = T(1))):
  \end{Mexin}
  \begin{Mexin}
g:=TM(2, 1, [T(infinity), T(1)]):
  \end{Mexin}
\begin{Mexin}
wa:=W(2, alphabet, l, m, g);
  \end{Mexin}
  \begin{Mexout}
                     +-             -+
+-           -+      |  1, infinity  |
| 1, infinity |, a = |               |,
+-           -+      |  1, infinity  |
                     +-             -+

       +-                    -+  +-          -+
       |  infinity, infinity  |  |  infinity  |
   b = |                      |, |            |
       |  infinity,     1     |  |      1     |
       +-                    -+  +-          -+
  \end{Mexout}
\begin{Mexin}
W::isAccessible(wa);
  \end{Mexin}
  \begin{Mexout}
                          FALSE, {1}
  \end{Mexout}

\begin{Mexin}
W::accessible(wa);
  \end{Mexin}
  \begin{Mexout}
       +- -+      +- -+      +-        -+  +-        -+
       | 1 |, a = | 1 |, b = | infinity |, | infinity |
       +- -+      +- -+      +-        -+  +-        -+
  \end{Mexout}

\begin{Mexin}
W::isCoaccessible(wa);
  \end{Mexin}
  \begin{Mexout}
                          FALSE, {2}
  \end{Mexout}

\begin{Mexin}
W::coaccessible(wa)
  \end{Mexin}
  \begin{Mexout}
       +-        -+      +-        -+      +- -+  +- -+
       | infinity |, a = | infinity |, b = | 1 |, | 1 |
       +-        -+      +-        -+      +- -+  +- -+
  \end{Mexout}
\begin{Mexin}
W::trim(wa)
  \end{Mexin}
  \begin{Mexout}
                   ++      ++      ++  +- -+
                   ||, a = ++, b = ++, +- -+
                   ++
  \end{Mexout}
\begin{Mexin}
W::isComplete(wa);
  \end{Mexin}
  \begin{Mexout}
                             FALSE
  \end{Mexout}

\begin{Mexin}
W::complete(wa);
  \end{Mexin}
  \begin{Mexout}
+-                     -+
| 1, infinity, infinity |, a =
+-                     -+

   +-                              -+
   |      1,    infinity, infinity  |
   |                                |
   |      1,    infinity, infinity  |,
   |                                |
   |  infinity, infinity,     0     |
   +-                              -+

       +-                              -+  +-          -+
       |  infinity, infinity,     0     |  |  infinity  |
       |                                |  |            |
   b = |  infinity,     1,    infinity  |, |      1     |
       |                                |  |            |
       |  infinity, infinity,     0     |  |  infinity  |
       +-                              -+  +-          -+
  \end{Mexout}

\end{MExample}
\begin{MExample}{ex5}
\eng{Deterministic automata can be computed:}

\begin{Mexin}
B:=Dom::BooleanSemiRing:
  \end{Mexin}

\begin{Mexin}
W:=Dom::WeightedAutomaton(B):
  \end{Mexin}

\begin{Mexin}
BM:=Dom::Matrix(B):
  \end{Mexin}

\begin{Mexin}
alphabet:=[a, b]:
  \end{Mexin}

\begin{Mexin}
l:=BM(1, 2, [0, 1]):
  \end{Mexin}

\begin{Mexin}
ma:=BM(2, 2, [[0, 1], [1, 1]]):
  \end{Mexin}

 \begin{Mexin}
mb:=BM(2, 2, [[1, 0], [1, 1]]):
  \end{Mexin}

  \begin{Mexin}
g:=BM(2, 1, [0, 1]):
  \end{Mexin}

\begin{Mexin}
wa:=W(2, alphabet, l, table(a = ma, b = mb), g)
  \end{Mexin}
  \begin{Mexout}
                     +-      -+      +-      -+  +-   -+
       +-    -+      |  0, 1  |      |  1, 0  |  |  0  |
       | 0, 1 |, a = |        |, b = |        |, |     |
       +-    -+      |  1, 1  |      |  1, 1  |  |  1  |
                     +-      -+      +-      -+  +-   -+
  \end{Mexout}

\begin{Mexin}
W::isDeterministic(wa)
  \end{Mexin}
  \begin{Mexout}
                             FALSE
  \end{Mexout}

\begin{Mexin}
W::determinization(wa)
  \end{Mexin}
  \begin{Mexout}
                     +-      -+      +-      -+  +-   -+
       +-    -+      |  0, 1  |      |  0, 1  |  |  1  |
       | 1, 0 |, a = |        |, b = |        |, |     |
       +-    -+      |  0, 1  |      |  0, 1  |  |  1  |
                     +-      -+      +-      -+  +-   -+
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex6}
\eng{Boolean operations are available:}
\begin{Mexin}
W::complementary(wa)
  \end{Mexin}
  \begin{Mexout}
                     +-      -+      +-      -+  +-   -+
       +-    -+      |  0, 1  |      |  0, 1  |  |  0  |
       | 1, 0 |, a = |        |, b = |        |, |     |
       +-    -+      |  0, 1  |      |  0, 1  |  |  0  |
                     +-      -+      +-      -+  +-   -+
  \end{Mexout}
\begin{Mexin}
I1:=BM(1, 1, [1]):
  \end{Mexin}
\begin{Mexin}
W(1, alphabet, I1, table(a = I1, b = I1), I1)
  \end{Mexin}
  \begin{Mexout}
              +- -+      +- -+      +- -+  +- -+
              | 1 |, a = | 1 |, b = | 1 |, | 1 |
              +- -+      +- -+      +- -+  +- -+
  \end{Mexout}
\begin{Mexin}
W::difference(wa, last(1))
  \end{Mexin}
  \begin{Mexout}
                     +-      -+      +-      -+  +-   -+
       +-    -+      |  0, 1  |      |  1, 0  |  |  0  |
       | 0, 1 |, a = |        |, b = |        |, |     |
       +-    -+      |  1, 1  |      |  1, 1  |  |  0  |
                     +-      -+      +-      -+  +-   -+
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex7}
\eng{Minimal automata can be computed:}
\begin{Mexin}
Z:=Dom::Integer:
\end{Mexin}
\begin{Mexin}
W:=Dom::WeightedAutomaton(Z):
\end{Mexin}
\begin{Mexin}
M:=Dom::Matrix(Z):
\end{Mexin}
\begin{Mexin}
alphabet:=[a, b]:
\end{Mexin}
\begin{Mexin}
l:=M(1, 3, [2, -1, 1]):
\end{Mexin}
\begin{Mexin}
ma:=M(3, 3, [[0, -1, 2], [1, 1, -1], [0, 0, 1]]):
\end{Mexin}
\begin{Mexin}
mb:=M(3, 3, [[-2, 0, 0], [0, -1, 2], [0, 0, -1]]):
\end{Mexin}
\begin{Mexin}
g:=M(3, 1, [1, -2, 0]):
\end{Mexin}
 \begin{Mexin}
aut:=W(3, alphabet, l, table(a = ma, b = mb), g);
  \end{Mexin}
  \begin{Mexout}
                  +-           -+      +-            -+
                  |  0, -1,  2  |      |  -2,  0,  0  |
+-        -+      |             |      |              |
| 2, -1, 1 |, a = |  1,  1, -1  |, b = |   0, -1,  2  |,
+-        -+      |             |      |              |
                  |  0,  0,  1  |      |   0,  0, -1  |
                  +-           -+      +-            -+

   +-    -+
   |   1  |
   |      |
   |  -2  |
   |      |
   |   0  |
   +-    -+
  \end{Mexout}
\begin{Mexin}
W::minimization(aut)
  \end{Mexin}
  \begin{Mexout}
                   +-        -+      +-        -+  +-    -+
   +-      -+      |  -4, -7  |      |   1,  3  |  |  -5  |
   | -5, -7 |, a = |          |, b = |          |, |      |
   +-      -+      |   3,  5  |      |  -2, -4  |  |   3  |
                   +-        -+      +-        -+  +-    -+
  \end{Mexout}

\begin{Mexin}
W::areEquivalent(aut, last(1))
  \end{Mexin}
  \begin{Mexout}
                             TRUE
  \end{Mexout}

\end{MExample}

\MSuperDomain{Dom::BaseDomain}

\begin{MChanges}
  \version{3.0}
  \new
\end{MChanges}

\end{Mhelppage}
