Here we study weighted automata which are finite, in the sense that the input alphabet is finite and the state space is of finite dimension. We also assume that the field is the field of reals.
A finite automaton can be represented in a finite way, call this the matrix representation. The state space must be isomorphic to , since these are the vector spaces of finite dimension. Therefore, it suffices to store
. For each input letter
, the transition function is a linear function
which can be stored as a matrix. (Here we assume that the entries of the matrix can be represented, which means either that we restrict to rational numbers, or use some computation model that can deal directly with real numbers.)
Computing reachable states
Let us begin with a simple algorithm for finite weighted automata – we want to compute the linear combinations of reachable states. This is a simple saturation procedure. We begin with being the singleton of the initial state. Then, assuming that
has already been defined, we define
to be the vector space spanned by
This way we get a growing chain of linear subsets
Since the dimension cannot grow indefinitely, this sequence must stabilise at some point, and this point is the set of reachable states. Furthermore, if the original automaton is given by a matrix representation, then one can compute the sets .
Computing automaton equivalence
Here is a corollary of the reachability algorithm. Suppose we want to test if two automata define the same function. We can define the product automaton, with states being pairs of stats from the two automata, and the output function being defined as
with being the output functions of the two original automata. In the product automaton we compute the linear combinations of reachable states. The automata were equivalent if and only if, when restricted to those states, the new output function is zero everywhere.
Computing the minimal automaton
Here we show that minimisation is effective, i.e. if one gets a finite weighted automaton on input, one can produce (even in polynomial time) the minimal automaton. Observe that if a function is recognised by a finite dimensional weighted automaton, then its syntactic automaton has finite dimension. This is because linear functions cannot increase dimension.
Consider a weighted automaton with a state space
of finite dimension. For a number
, we define states
to be
-equivalent if
holds for all input words of length at most , where
if the output of the automaton after reading word
assuming that the initial state was changed to
. This equivalence relation can be seen as a subset of
. By linearity of the automaton, the subset is linear, i.e. it is closed under and multiplying by scalars. Therefore we have a sequence of subsets
which are linear. Since each subset has a dimension, which is at most double the dimension of , the sequence above must stabilise at some equivalence relation, call it
, which is the Myhill-Nerode equivalence relation. Furthermore, a representation of this
can be computed in time polynomial in the dimension of the original automaton. The remaining description is essentially book-keeping: we prove that there is a well-defined quotient automaton, and that a matrix representation of it can be computed based on a matrix representation of the original automaton.
Let be the set of equivalence classes of
with respect to
, and let
be the function which maps a state to its equivalence class. Because is an equivalence relation and a linear set, the set
is a vector space, and
is a linear function. What is the dimension of
and how do we represent it and the function
, assuming that
for some
? One solution is the following. Begin with
being some basis of
, e.g. the
vectors which have
on a unique coordinate. Then, iterate the following: check if there is some
which is equivalent under
to a linear combination of other elements of
. If there is no such
, then return
, otherwise remove one such
from
and continue the process. At the end we get a subset
, such that every element of
is equivalent under
to a linear combination of vectors from
. In particular,
is isomorphic to
. Out of this process we also get a matrix representation of the function
, seen as a linear function
.
If we take two states that are equivalent under , and apply to them a transition function
then the results are also equivalent. This means that for every input letter
there exists a function
which makes the following diagram commute:
The function is also linear, because its graph, as a subset of
, is simply the image of the graph of
under
applied coordinatewise. In particular, we can compute a matrix representing each function
. A similar argument proves that there is a linear function
which makes the following diagram commute
and a matrix representing it can be computed.
This finishes the description of the algorithm for minimising finite weighted automata.
Leave a Reply