[Previous] [Next] [Contents]

## `Dom::WeightedAutomaton` -- set of weighted automata

#### Introduction

`Dom::WeightedAutomaton``(S)` creates a domain for weighted automata with multiplicities in the component semi-ring `S`.

#### Domain

`Dom::WeightedAutomaton(S)`

#### Parameters

`S` | - | a semi-ring, i.e., a domain of category Cat::SemiRing

#### Introduction

The domain element `Dom::WeightedAutomaton``(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.

#### Creating Elements

``Dom::WeightedAutomaton`(S)(n,A,i,t,f)`

#### Parameters

`n` | - | positive integer.
`A` | - | list.
`i` | - | 1×n sparse matrix over S.
`t` | - | table indexed by elements of A whose the values are n×n sparse matrices over S.
`f` | - | n×1 sparse matrix over S.

#### Related Domains

`Dom::BooleanSemiRing`, `Dom::MaxMinSemiRing`, `Dom::MaxPlusSemiRing`, `Dom::MinMaxSemiRing`, `Dom::MinPlusSemiRing.`

#### Method weight: weight of a word

- `weight(dom wa, DOM_LIST u)`

- The weight of the word `u` given by a list `[u1,u2,...,uk]` is defined to be the product of sparse matrices `i*t[u1]*t[u2]*...*t[uk]*f`.

#### Method proper: proper automaton of a weighted automaton

- `proper(dom wa)`

- The proper automaton of a weighted automaton keeps the same behaviour with the weight 0 for the empty word `[]`.

#### Method automatdim: dimension of a weighted automaton

- `automatdim(dom wa)`

- The dimension of a weighted automaton is defined to be the dimension of transition matrices.

#### Method automatalph: alphabet of a weighted automaton

- `automatalph(dom wa)`

- The alphabet of the weighted automaton is computed.

#### Method automatinit: initial vector of a weighted automaton

- `automatinit(dom wa)`

- The initial vector of the weighted automaton is computed.

#### Method automattrans: transition matrix of a weighted automaton

- `automattrans(dom wa <any x>)`

- The transition function of the weighted automaton is returned if `x` is not given, the transition matrix of `x` otherwise.

#### Method automatfin: final vector of a weighted automaton

- `automatfin(dom wa)`

- The final vector of the weighted automaton is computed.

#### Method tensor: Kronecker product of sparse matrices

- `tensor(Dom::SparseMatrix(S) A,Dom::SparseMatrix(S) B)`

- The Kronecker product of the sparse matrices `A` and `B` is computed.

#### Method mstar: Star of a sparse matrix

- `mstar(Dom::SparseMatrix(S) A)`

- The star of the sparse matrix `A` is computed.

#### Method _plus: sum of weighted automata

- `_plus(dom wa1...)`

- The sum `wa1+wa2+...+wak` of weighted automata is defined to be the weighted automaton with c1+c2+...+ck the weight of a word u if ci is the weight of u for the automaton `wai`.
- This method overloads the function `_plus`.

#### Method _mult: Cauchy product of weighted automata

- `_mult(dom wa1...)`

- The Cauchy product `wa1*wa2*...*wak` of weighted automata is defined to be the weighted automaton with ∑c1*c2*...*ck the weight of a word u if ci is the weight of the word ui for the automaton `wai` for each decomposition u=u1u2...uk.
- This method overloads the function `_mult`.

#### Method hadamard: Hadamard product of weighted automata

- `hadamard(dom wa1,dom wa2)`

- The Hadamard product of two weighted automata `wa1` and `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 `wai`.

#### Method shuffle: shuffle product of weighted automata

- `shuffle(dom wa1,dom wa2)`

- The shuffle product of two weighted automata `wa1` and `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 `wa1` and `wa2`.

#### Method infiltration: infiltration product of weighted automata

- `infiltration(dom wa1,dom wa2)`

- The infiltration product of two weighted automata `wa1` and `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 `wa1` and `wa2`.

#### Method star: star of a weighted automaton

- `star(dom wa)`

- The star of a weighted automaton `wa` with the rational noncommutative formal series S as behaviour is returned with the star of S (if there exists) as behaviour.

#### Method elimination: elimination of a letter in a weighted automaton

- `elimination(dom wa,any x)`

- The x-removing of a weighted automaton `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 `x` and the old transition matrix.

<<<<<<< WeightedAutomaton.tex

#### Method isdeterministic: checks whether a weighted automaton is deterministic

- `isdeterministic(dom wa)`

- This method return TRUE if the weighted automaton wa is deterministic, and FALSE otherwise.

#### Method determinization: determinization of a weighted automaton

- `determinization(dom wa)`

- This method return the determinization of the weighted automaton wa if is possible, and FAIL otherwise.

#### Method convert_to: conversion of a weighted automaton to a weighted automaton over another semi-ring

- `convert_to(dom wa, any T)`

- Tries to convert the weighted automaton `wa` into a weighted automaton over scalars of type `T`.

=======

#### Method isdeterministic: checks whether a weighted automaton is deterministic

- `isdeterministic(dom wa)`

- This method return TRUE if the weighted automaton wa is deterministic, and FALSE otherwise.

#### Method determinization: determinization of a weighted automaton

- `determinization(dom wa)`

- This method return the determinization of the weighted automaton wa if is possible, and FAIL otherwise.

#### Method convert_to: conversion of a weighted automaton to a weighted automaton over another semi-ring

- `convert_to(dom wa, any T)`

- Tries to convert the weighted automaton `wa` into a weighted automaton over scalars of type `T`.

>>>>>>> 1.6

#### Example 1

<<<<<<< WeightedAutomaton.tex

We construct weighted automata with multiplicities in the MinPlus semi-ring:

=======

We construct weighted automata with multiplicities in the MinPlus semi-ring:

>>>>>>> 1.6

    >> T:=Dom::MinPlusSemiRing():

    >> W:=Dom::WeightedAutomaton(T):

    >> TM:=Dom::SparseMatrix(T):

    >> alphabet1:=[a,b]: alphabet2:=[a,c]:

    >> l1:=TM(1,2,[T(2),T(infinity)]):

    >> l2:=TM(1,3,[T(1),T(0),T(1)]):

    >> m1[a]:=TM(2,2,[[T(0),T(1)],[T(1),T(infinity)]]):

    >> m1[b]:=TM(2,2,[[T(infinity),T(0)],[T(1),T(1)]]):

    >> m2[a]:=TM(3,3,[[T(2),T(1),T(infinity)],[T(1),T(0),T(0)],[T(1),T(infinity),
       T(2)]]):

    >> m2[c]:=TM(3,3,[[T(1),T(infinity),T(0)],[T(2),T(2),T(infinity)],[T(infinity),
       T(1),T(0)]]):

    >> g1:=TM(2,1,[T(0),T(1)]):

    >> g2:=TM(3,1,[T(infinity),T(0),T(1)]):

    >> wa1:=W(2,alphabet1,l1,m1,g1);

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

             +-   -+
             |  0  |
             |     |
             |  1  |
             +-   -+

    >> wa2:=W(3,alphabet2,l2,m2,g2);

                           +-                       -+
                           |  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     |
                 +-                              -+  +-          -+

#### Example 2

The weight of a word is computed:

    >> W::weight(wa1, [a, a, b, a])

                                         3

#### Example 3

Some functionalities on weighted automata are presented:

    >> W::proper(wa1)

                                         +-                       -+
                                         |  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     |
                 +-                       -+  +-          -+

    >> wa1 + wa2

          +-                    -+
          | 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     |
             +-          -+

    >> wa1*wa2

          +-                                         -+
          | 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     |
             +-          -+

    >> W::hadamard(wa1, wa2)

          +-                                     -+
          | 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     |
             +-          -+

    >> W::shuffle(wa1, wa1)

          +-                               -+
          | 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  |
                 +-                                        -+  +-   -+

    >> W::star(wa1)

                                         +-                -+
                                         |  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  |
                 +-                       -+  +-   -+

    >> W::elimination(wa1, a)

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

#### Example 4

Deterministic automata can be computed:

    >> B:=Dom::BooleanSemiRing:

    >> W:=Dom::WeightedAutomaton(B):

    >> BM:=Dom::SparseMatrix(B):

    >> alphabet:=[a, b]:

    >> l:=BM(1, 2, [0, 1]):

    >> ma:=BM(2, 2, [[0, 1], [1, 1]]):

    >> mb:=BM(2, 2, [[1, 0], [1, 1]]):

    >> g:=BM(2, 1, [0, 1]):

    >> wa:=W(2, alphabet, l, table(a = ma, b = mb), g)

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

    >> W::isdeterministic(wa)

                                       FALSE

    >> W::determinization(wa)

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

#### Super-Domain

`Dom::BaseDomain`

#### Changes

- `Dom::WeightedAutomaton` is a new function

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package