[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

Method proper: proper automaton of a weighted automaton

Method automatdim: dimension of a weighted automaton

Method automatalph: alphabet of a weighted automaton

Method automatinit: initial vector of a weighted automaton

Method automattrans: transition matrix of a weighted automaton

Method automatfin: final vector of a weighted automaton

Method tensor: Kronecker product of sparse matrices

Method mstar: Star of a sparse matrix

Method _plus: sum of weighted automata

Method _mult: Cauchy product of weighted automata

Method hadamard: Hadamard product of weighted automata

Method shuffle: shuffle product of weighted automata

Method infiltration: infiltration product of weighted automata

Method star: star of a weighted automaton

Method elimination: elimination of a letter in a weighted automaton

<<<<<<< WeightedAutomaton.tex

Method isdeterministic: checks whether a weighted automaton is deterministic

Method determinization: determinization of a weighted automaton

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

=======

Method isdeterministic: checks whether a weighted automaton is deterministic

Method determinization: determinization of a weighted automaton

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

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

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package