Dom::WeightedAutomaton
--
set of weighted automata
Dom::WeightedAutomaton
(S)
creates a domain for weighted automata with
multiplicities in the component semi-ring S
.
Dom::WeightedAutomaton(S)
S | - | a semi-ring, i.e., a domain of category Cat::SemiRing |
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.
Dom::WeightedAutomaton
(S)(n,A,i,t,f)
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. |
Dom::BooleanSemiRing
, Dom::MaxMinSemiRing
, Dom::MaxPlusSemiRing
, Dom::MinMaxSemiRing
, Dom::MinPlusSemiRing.
weight(dom wa, DOM_LIST u)
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
.
proper(dom wa)
[]
.
automatdim(dom wa)
automatalph(dom wa)
automatinit(dom wa)
automattrans(dom wa <any x>)
x
is not given, the transition matrix of x
otherwise.
automatfin(dom wa)
tensor(Dom::SparseMatrix(S) A,Dom::SparseMatrix(S) B)
A
and B
is
computed.
mstar(Dom::SparseMatrix(S) A)
A
is computed.
_plus(dom wa1...)
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
._plus
.
_mult(dom wa1...)
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._mult
.
hadamard(dom wa1,dom wa2)
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
.
shuffle(dom wa1,dom wa2)
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
.
infiltration(dom wa1,dom wa2)
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
.
star(dom wa)
wa
with the rational
noncommutative formal series S as behaviour is returned with the star of
S (if there exists) as behaviour.
elimination(dom wa,any x)
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
isdeterministic(dom wa)
determinization(dom wa)
convert_to(dom wa, any T)
wa
into a weighted
automaton over scalars of type T
.=======
isdeterministic(dom wa)
determinization(dom wa)
convert_to(dom wa, any T)
wa
into a weighted
automaton over scalars of type T
.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 | +- -+ +- -+
The weight of a word is computed:
>> W::weight(wa1, [a, a, b, a])
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 | +- -+ +- -+
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 | +- -+ +- -+ +- -+
Dom::WeightedAutomaton
is a new function
MuPAD Combinat, an open source algebraic combinatorics package