On the Determinization of Weighted Finite Automata.
We study the problem of constructing the deterministic equivalent of a nondeterministic weighted finite-state automaton (WFA). Determinization of WFAs has important applications in automatic speech recognition (ASR). We provide the first polynomial-time algorithm to test for the  twins property, which determines if a WFA admits a deterministic equivalent. We also give upper bounds on the size of the deterministic equivalent; the bound is tight in the case of acyclic WFAs. Previously, Mohri presented a superpolynomial-time algorithm to test for the twins property, and he also gave an algorithm to determinize WFAs. He showed that the latter runs in time linear in the size of the output when a deterministic equivalent exists; otherwise, it does not terminate. Our bounds imply an upper bound on the running time of this algorithm.Given that WFAs can expand exponentially in size when determinized, we explore why those that occur in ASR tend to  shrink when determinized. According to ASR folklore, this phenomenon is attributable solely to the fact that ASR WFAs have simple topology, in particular, that they are acyclic and layered. We introduce a very simple class of WFAs with this structure,  but we show that the expansion under determinization depends on the transition weights: some weightings cause them to shrink, while others, including random weightings, cause them to expand exponentially. We provide experimental evidence that ASR WFAs exhibit this weight dependence. That they shrink when determinized, therefore, is a result of favorable weightings in addition to special topology. These analyses and observations have been used to design a new, approximate WFA determinization algorithm, reported in a separate paper along with experimental results showing that it achieves significant WFA size reduction with negligible impact on ASR performance.
Introduction
Finite-state machines and their relation to rational functions and power series have been
extensively studied [2, 3, 12, 16] and widely applied in fields ranging from image compression
[9-11, 14] to natural language processing [17, 18, 24, 26]. A subclass of finite-state
machines, the weighted finite-state automata (WFAs), has recently assumed new
importance, because WFAs provide a powerful method for manipulating models of human
language in automatic speech recognition (ASR) systems [19, 20]. This new re-search
direction also raises a number of challenging algorithmic questions [5].
A weighted finite-state automaton (WFA) is a nondeterministic finite automaton
(NFA), A, that has both an alphabet symbol and a weight, from some set K, on each
transition.
be a semiring. Then A together with R generates a
partial function from strings to K: the value of an accepted string is the semiring sum
over accepting paths of the semiring product of the weights along each accepting path.
Such a partial function is a rational power series [25]. An important example in ASR
is the set of WFAs with the min-sum semiring, which
compute for each accepted string the minimum cost accepting path.
In this paper, we study problems related to the determinization of WFAs. A deter-
ministic, or sequential, WFA has at most one transition with a given input symbol out
of each state. Not all rational power series can be generated by deterministic WFAs. A
determinization algorithm takes as input a WFA and produces a deterministic WFA that
generates the same rational power series, if one exists. The importance of determinization
to ASR is well established [17, 19, 20].
As far as we know, Mohri [17] presented the first determinization procedure for
WFAs, extending the seminal ideas of Choffrut [7, 8] and Weber and Klemm [27] regarding
string-to-string transducers. Mohri gives a determinization procedure with three
phases. First, A is converted to an equivalent unambiguous, trim WFA A t , using an algorithm
analogous to one for NFAs [12]. (Unambiguous and trim are defined below.)
Mohri then gives an algorithm, TT, that determines if A t has the twins property (also
defined below). If A t does not have the twins property, then there is no deterministic
equivalent of A. If A t has the twins property, a second algorithm of Mohri's, DTA, can
be applied to A t to yield A 0 , a deterministic equivalent of A. Algorithm TT runs in
O(m 4n 2
is the number of transitions and n the number of states in A t .
Algorithm runs in time linear in the size of A 0 . Mohri observes that A 0 can be
exponentially larger than A, because WFAs include classical NFAs. He gives no upper
bound on the worst-case state-space expansion, however, and due to weights, the classical
NFA upper bound does not apply. Finally, Mohri gives an algorithm that takes a
deterministic WFA and outputs the minimum-size equivalent, deterministic WFA.
In this paper, we present several results related to the determinization of WFAs. In
Section 3 we give the first polynomial-time algorithm to test whether an unambiguous,
WFA satisfies the twins property. It runs in O(m 2 n 6 ) time. We then provide a
worst-case time complexity analysis of DTA. The number of states in the output deterministic
WFA is at most 2 n(2 lg n+n 2 lg j\Sigmaj+1) , where \Sigma is the input alphabet. If the
weights are rational, this bound becomes 2 n(2 lg n+1+min(n 2 lg j\Sigmaj;ae)) , where ae is the
maximum bit-size of a weight. When the input WFA is acyclic, the bound becomes
which is tight (up to constant factors) for any alphabet size.
In Sections 4-6 we study questions motivated by the use of WFA determinization
in ASR [19, 20]. Although determinization causes exponential state-space expansion
in the worst case, in ASR systems the determinized WFAs are often smaller than the
input WFAs [17]. This is fortuitous, because the performance of ASR systems depends
directly on WFA size [19, 20]. We study why such size reductions occur. The folklore
explanation within the ASR community credits special topology-the underlying
directed graph, ignoring weights-for this phenomenon. ASR WFAs tend to be multipartite
and acyclic. Such a WFA always admits a deterministic equivalent.
In Section 4 we exhibit multi-partite, acyclic WFAs whose minimum equivalent deterministic
WFAs are exponentially larger. In Section 5 we study a class of WFAs, RG,
with a simple multi-partite, acyclic topology, such that in the absence of weights the deterministic
equivalent is smaller. We show that for any A 2 RG and any i - n, there exists
an assignment of weights to A such that the minimal equivalent deterministic WFA
has states. Using ideas from universal hashing, we show that similar results
hold when the weights are random i-bit numbers. We call a WFA weight-dependent if
its expansion under determinization is strongly determined by its weights.
We examined experimentally the effect of varying weights on actual WFAs from
ASR applications. In Section 6 we give results of these experiments. Most of the ASR
examples were weight-dependent. These experimental results together with the theory
we develop show that the folklore explanation is insufficient: ASR WFAs shrink under
determinization because both the topology and weighting tend to be favorable.
Some of our results help explain the nature of WFAs from the algorithmic point of
view, i.e., how weights assigned to the transitions of a WFA can affect the performance
of algorithms manipulating it. Others relate directly to the theory of weighted automata.
Definitions and Terminology
Given a semiring (K;
weighted finite automaton (WFA) is a tuple
is the set of states, - q 2 Q is the initial state, \Sigma is the set
of symbols, ffi ' Q \Theta \Sigma \Theta K \Theta Q is the set of transitions, and Q f ' Q is the set of
final states. We assume throughout that j\Sigma j ? 1. A deterministic, or sequential, WFA
has at most one transition
WFA can have multiple transitions on a pair (q 1 ; oe), differing in target state q 2 . The
problems examined in this paper are motivated primarily by ASR applications, which
work with the min-sum semiring, Furthermore, some of
the algorithms considered use subtraction, which the min-sum semiring admits. We thus
limit further discussion to the min-sum semiring.
Consider a sequence of transitions
t induces string String w is accepted by t if q
q and q ' 2
accepted by G if some t accepts w. Let c(t i be the weight of t i . The weight of
t is
(w) be the set of all sequences of transitions that accept
string w. The weight of w is The weighted language of G is
the set of weighted strings accepted by G: accepted by Gg :
Intuitively, the weight on a transition of G can be seen as the "confidence" one has in
taking that transition. The weights need not, however, satisfy stochastic constraints, as
do the probabilistic automata introduced by Rabin [22].
Fix two states q and q 0 and a string v 2 \Sigma   . Then c(q; v; q 0 ) is the minimum of
taken over all transition sequences from q to q 0 generating v. We refer to c(q; v; q 0 )
as the optimal cost of generating v from q to q 0 . We generally abuse notation so that
ffi(q; w) can represent the set of states reachable from state q 2 Q on string w 2 \Sigma   .
We extend the function ffi to strings in the usual way: q means that
there is a sequence of transitions from q to q 0 generating v.
The topology of G, top(G), is the projection -Q\Theta\Sigma \ThetaQ (ffi): i.e., the transitions of G
without respect to the weights. We also refer to top(G) as the graph underlying G.
A WFA is trim if every state appears in an accepting path for some string and no
transition is weighted - 0 (1 in the min-sum semiring). A WFA is unambiguous if there
is exactly one accepting path for each accepted string.
Determinization of G is the problem of computing a deterministic WFA G 0 such
that if such a G 0 exists. We denote the output of algorithm DTA by
dta(G). We denote the minimal deterministic WFA accepting L(G) by min(G), if one
exists. We say that G expands if dta(G) has more states and/or transitions than G.
let the size of G be n m. We assume that each
transition is labeled with exactly one symbol, so j\Sigma j - m. Recall that the weights
of G are non-negative real numbers. Let C be the maximum weight. In the general
case, weights are incommensurable real numbers, requiring "infinite precision." In the
integer case, weights can be represented with bits. We denote the integral
range [a; b] by [a; b] Z . The integer case extends to the case in which the weights are
rationals requiring ae bits. We assume that in the integer and rational cases, weights are
normalized to remove excess least-significant zero bits.
For our analyses, we use the RAM model of computation as follows. In the general
case, we charge constant time for each arithmetic-logic operation involving weights
(which are real numbers). We refer to this model as the !-RAM [21]. The relevant
parameters for our analyses are n, m, and j\Sigma j. In the integer case, we also use a RAM,
except that each arithmetic-logic operation now takes O(ae) time. We refer to this model
as the CO-RAM [1]. The relevant parameters for the analyses are n, m, j\Sigma j, and ae.
3 Determinization of WFAs
3.1 An Algorithm for Testing the Twins Property
Definition 1. Two states, q and q 0 , of a WFA G are twins if 8(u; v) 2 (\Sigma   ) 2 such
that q 2 ffi( -
the following holds:
c(q; v; has the twins property if all pairs q; q 0 2 Q are twins.
That is, if states q and q 0 are reachable from -
q by a common string, then q and q 0
are twins only if any string that induces a cycle at each induces cycles of equal optimal
cost. Note that two states having no cycle on a common string are twins.
G be a trim, unambiguous WFA. G has the twins
property if and only if 8(u; v) 2 (\Sigma   ) 2 such that juvj - 2n the following holds:
when there exist two states q and q 0 such that (i) fq; q 0 g ' ffi( -
q; u), and (ii) q 2 ffi(q; v)
and must follow.
are analogous to those stated by Choffrut [7, 8] and (in
different terms) by Weber and Klemm [27] to identify necessary and sufficient conditions
for a string-to-string transducer to admit a sequential transducer realizing the
same rational transduction. The proof techniques used for WFAs differ from those used
to obtain analogous results for string-to-string transducers, however. In particular, the
efficient algorithm we derive here to test a WFA for twins is not related to that of Weber
and Klemm [27] for testing twins in string-to-string transducers.
We define T - q;-q , a multi-partite, acyclic, labeled, weighted graph having 2n 2 layers,
as follows. The root vertex comprises layer zero and corresponds to (-q; - q). For i ? 0,
given the vertices at layer i \Gamma 1, we obtain the vertices at layer i as follows. Let u be a
vertex at layer corresponding to (q 1 connected to u 0 , corresponding
to (q 0
2 ), at layer i if and only if there are two distinct transitions
and
G. The arc connecting u to u 0 is labeled with a 2 \Sigma and
has cost
q;-q has at most 2n
Let (q; q 0 ) i be the vertex corresponding to (q; q 0 at layer i of T - q;-q , if any. Let
be the set of pairs of distinct states of G that are reachable
from (-q; -
q;-q . For each (q; q 0 analogously to T -
q;-q .
Fix two distinct states q and q 0 of G. Let (q; q 0
, be all the occurrences of (q; q 0 ) in T q;q 0 , excluding (q; q 0 ) 0 . This sequence
may be empty. A symmetric sequence can be extracted from T q 0 ;q . We refer to these
sequences as the common cycles sequences of (q; q 0 ). We say that q and q 0 satisfy the
local twins property if and only if (a) their common cycles sequences are empty or (b)
zero is the cost of (any) shortest path from (q; q 0 ) 0 to (q; q 0 and from (q
to
Lemma 2. Let G be a trim, unambiguous WFA. G satisfies the twins property if and
only if (i) RT is empty or (ii) all (q; q 0 the local twins property.
Proof (Sketch). We outline the proof for the sufficient condition. The only nontrivial
case is when some states in RT satisfy the local twins property and their common cycles
sequences are not empty. Let RT 0 be such a set. Assume that G does not satisfy the
twins property. We derive a contradiction. Since RT 0 is not empty, we have that the set
of pairs of states for which (i) and (ii) are satisfied in Lemma 1 is not empty. But since
G does not satisfy the twins property, there must exist two states q and q 0 and a string
1, such that (i) both q and q 0 can be reached from the initial
state of G through string u; (ii) q 2 ffi(q; v) and q
loss of generality, assume that
Now, one can show that (q; q 0 using the fact that G is unambiguous,
one can show that there is exactly one path in T q;q 0 from the root to (q; q 0 ) jvj with cost
the local twins property.
To test whether a trim, unambiguous WFA has the twins property, we first compute
q;-q and the set RT . For each pair of states (q; q 0 that has not yet been processed,
we need only compute T q;q 0 and T q 0 ;q and their respective shortest path trees.
Theorem 1. Let G be a trim unambiguous WFA. In the general case, whether G satisfies
the twins property can be checked in O(m using the !-RAM. In the integer
case, the bound becomes O(aem using the CO-RAM.
3.2 The
In this section we describe the algorithm. We then give an upper bound on the
size of the deterministic machines produced by the algorithm. The results of Section 5
below show that our upper bound is tight to within polynomial factors.
Given WFA
generalizes the classic power-set construction
to construct deterministic WFA G 0 as follows. The start state of G 0 is f(-q; 0)g,
which forms an initial queue P . While P 6= ;, pop state
from P , where q 1g. The r i values encode path-length infor-
mation, as follows. For each oe 2 \Sigma , let fq 0
m g be the set of states reachable by
oe-transitions out of all the q i . For
be the minimum of the weights of oe-transitions into q 0
j from the q i plus the respective
g. Let q
m. We add transition (q; oe; ae; q 0 ) to G 0 and push q 0 onto P if q 0 is new. This is
the only oe-transition out of state q, so G 0 is deterministic.
Let TG (w) be the set of sequences of transitions in G that accept a string w 2 \Sigma   ;
let t G 0 (w) be the (one) sequence of transitions in G 0 that accepts the same string. Mohri
[17] shows that c(t G 0
let be the set of sequences of transitions in G from state -
q to state q that induce
string w. Again, let t G 0 (w) be the (one) sequence of transitions in G 0 that induces the
same string; t G 0 (w) ends at some state f(q 1 such that some
shows that c(t G Thus, each r i is
a remainder that encodes the difference between the weight of the shortest path to some
state that induces w in G and the weight of the path inducing w in G 0 . Hence at least
one remainder in each state must be zero.
3.3 Analyzing
We first bound the number of states in dta(G), denoted #dta(G).
Theorem 2. If WFA G has the twins property, then
in the general case; in the integer (or rational)
case; and #dta(G) ! 2 n lg j\Sigmaj if G is acyclic, independent of any assumptions on
weights. The acyclic bound is tight (up to constant factors) for any alphabet.
Proof (Sketch). Let ~
R be the set of remainders in dta(G). Let R be the set of remainders
r for which the following holds: 9w 2 \Sigma   , jwj - and two states q 1 and q 2 ,
such that )j. The twins property implies that ~
R ' R. In the
worst case, each i-state tuple from G will appear in dta(G), and there are j ~
i-tuples of remainders it can assume. (This over counts by including tuples without any
zero remainders.) Therefore, #dta(G) -
General Case: Each string of length at most n reach a pair of (not necessarily
distinct) states in G. Therefore, jRj
. Integer Case: The remainders in
R are in [0; (n
. Acyclic Case:
#dta(G) is bounded by the number of strings in the weighted language accepted by G,
which is bounded by j\Sigma j n . We discuss tightness in Section 5.
Processing each tuple of state-remainders generated by
time, excluding the cost of arithmetic and min operations, yielding the following.
Theorem 3. Let G be a WFA satisfying the twins property. In the general case,
takes O(j\Sigmaj(n on the !-RAM. In the (rational or) integer
case, on the CO-
RAM. In the acyclic case, takes O(j\Sigmaj(n +m)2 n lg j\Sigmaj ) time on the !-RAM and
O(aej\Sigmaj(n +m)2 n lg j\Sigmaj ) time on the CO-RAM.
We can use the above results to generate hard instances for any determinization
algorithm. A reweighting function (or simply reweighting) f is such that, when applied
to a WFA G, it preserves the topology of G but possibly changes the weights. We want
to determine a reweighting f such that min(f(G)) exists and jmin(f(G))j is maximized
among reweightings for which min(f(G)) exists. We restrict attention to the integer
case and, without loss of generality, we assume that G is trim and unambiguous.
Theorem 2 shows that for weights to affect the growth of dta(G), it must
be that ae - n 2 lg j\Sigma j. Set ae To find the required reweight-
ing, we simply consider all possible reweightings of G satisfying the twins property
and requiring at most ae max bits. There are (2 ae possible
reweightings, and it takes 2 O(n(2 lg n+(n 2 lg j\Sigmaj))) time to compute the expansion or decide
that the resulting machine cannot be determinized, bounding the total time by
4 Hot Automata
This section provides a family of acyclic, multi-partite WFAs that are hot: when de-
terminized, they expand independently of the weights on their transitions. Given some
alphabet an g, consider the language
i.e., the
set of all n-length strings that do not include all symbols from \Sigma . It is simple to obtain
an acyclic, multi-partite NFA H of poly(n) size that accepts L. It is not hard to show
that the minimal DFA accepting L has \Theta(2 n+lg n ) states. Furthermore, we can construct
H so that these bounds hold for a binary alphabet. H corresponds to a WFA with
all arcs weighted identically. Since acyclic WFAs satisfy the twins property, they can
always be determinized. Altering the weights can only increase the expansion. Kintala
and Wotschke [15] provide a set of NFAs that produces a hierarchy of expansion factors
when determinized, providing additional examples of hot WFAs.
5 Weight-Dependent Automata
In this section we study a simple family of WFAs with multi-partite, acyclic topology.
We examine how various reweightings affect the size of the determinized equivalent.
This family shrinks without weights, so any expansion is due to weighting. This study
is related in spirit to previous works on measuring nondeterminism in finite automata
[13,15]. Here, however, nondeterminism is encoded only in the weights. We first discuss
the case of a binary alphabet and then generalize to arbitrary alphabets.
5.1 The Rail Graph
We denote by RG(k) the k-layer rail graph. RG(k) has 2k
g. There are arcs (0;
See Fig. 1. RG(k) is 1)-partite and also has fixed in- and out-degrees. If we consider
the strings induced by paths from 0 to either T k or B k , then the language of RG(k)
is the set of strings LRG . The only nondeterministic choice is at the state
0, where either the top or bottom rail may be selected. Hence a string w can be accepted
by one of two paths, one following the top rail and the other the bottom rail.
a
a
a
a
a
a
a
a
a
a
Fig. 1. Topology of the k-layer rail graph.
Technically, RG(k) is ambiguous. We can disambiguate RG(k) by adding transitions
from T k and B k , each on a distinct symbol, to a new final state. Our results extend
to this case. For clarity of presentation, we discuss the ambiguous rail graph.
The rail graph is weight-dependent. In Section 5.2 we provide weightings such that
produces the (k+1)-vertex trivial series-parallel graph: a graph on k+1 vertices,
with transitions, on all symbols, only between vertices i and i+1, for 1 - i - k. On the
other hand, in Section 5.3 we exhibit weightings for the rail graph that cause DTA to
produce exponential state-space expansions. We also explore the relationship between
the magnitude of the weights and the amount of expansion that is possible. In Section
5.4, we show that random weightings induce the behavior of worst-case weightings.
Finally, in Section 5.5 we generalize the rail graph to arbitrary alphabets.
5.2 Weighting RG(k)
Consider determinizing RG(k) with DTA. The set of states reachable on any string
g. For a given weighting function c, let
c T (w) denote the cost of accepting string w if the top path is taken; i.e., c T
Analogously define c B (w) to be the corresponding
cost along the bottom path. Let R(w) be the remainder vector for w, which is a pair
of the form (0; c B 0). A state at layer 0
in the determinized WFA is labeled (fT string w leading to that
state. Thus, two strings w 1 and w 2 of identical length lead to distinct states in the determinized
version of the rail graph if and only if R(w 1
It is convenient simply to write (w). The sign of R(w) then
determines which of the two forms (0; x) or (x; 0) of the remainder vector occurs.
denote the weight on the top (rsp., bottom) arc labeled oe
into vertex T
Theorem 4. There is a reweighting f such that
which consists of the series-parallel graph
Proof. Any f for which suffices, since in this case R(w 1
g. In particular, giving zero weights suffices.
5.3 Worst-Case Weightings of RG(k)
Theorem 5. For any j 2 [0; k] Z there is a reweighting f such that layers 0 through j
of dta(f(RG(k))) form the complete binary tree on 2 vertices.
Proof (Sketch). Choose any weighting such that
Consider a pair of strings w
identical length such that w 1 6= w 2 . The weighting ensures that R(w 1
Theorem 6. For any j 2 [0; k] Z there is a reweighting f such that layers 0 through
the complete binary tree on vertices.
Theorem 6, generalized by Theorem 10, shows that weight-dependence is not an
artifact of DTA and that the acyclic bound of Theorem 2 is tight for binary alphabets.
We now address the sensitivity of the size expansion to the magnitude of the
weights, arguing that exponential state-space expansion requires exponentially big
weights for the rail graph. (This means that the size expansion, while exponential in
the number of states, is only super-polynomial in the number of bits.)
Theorem 7. Let f be a reweighting. If jdta(f(RG(k)))j
are
required to encode f(RG(k)).
Proof (Sketch). There must
be\Omega remainders among the states at depth k in
the determinized WFA,
necessitating\Omega distinct permutations of the d k
bits among them.
Thus\Omega (k) weights must have similarly high-order bits set.
Corollary 1. Let f be a reweighting. If jmin(f(RG(k)))j
are required to encode f(RG(k)).
5.4 Random Weightings of RG(k)
Theorem 8. Let G be RG(k) weighted with numbers chosen independently and uniformly
at random from [1;
denotes the expected value of the random variable X .
Theorem 9. Let G be RG(k) weighted with logarithms of numbers chosen independently
and uniformly at random from [1;
The proofs of Theorems 8 and 9 use the observation that the random functions
defined by RG are essentially universal hash functions [6] to bound sufficiently low the
probability that the remainders of two distinct strings are equal. Theorem 9 is motivated
by the fact that the weights of ASR WFAs are negated log probabilities.
Extending RG(k) to Arbitrary Alphabets
We can extend the rail graph to arbitrary alphabets, defining RG(r; k), the k-layer r-
rail graph, as follows. RG(r;
. Assume the alphabet is
for all 1 -
The subgraph induced by vertex 0 and vertices v i
comprises rail i of RG(r; k). The subgraph induced by vertices
and some j comprises layer j of RG(r; k). Vertex 0 comprises layer 0 of RG(r; k).
Thus, RG(2; k) is the k-layer rail graph, RG(k), defined in Section 5.1.
Let c(i; j; s) be the weight of the arc labeled s into vertex v i
Theorems 4 and 5
generalize easily to the k-layer r-rail graphs. Theorem 6 generalizes to RG(r;
follows, showing that the acyclic bound of Theorem 2 is tight for arbitrary alphabets.
Theorem 10. For any j 2 [0; k] Z there is a reweighting f such that layers 0 through
the complete r-ary tree on r j \Gamma1
vertices.
Proof (Sketch). Choose the following weighting. Set c(i; ';
for all 1 -
Given two strings, w 1 6= w 2 , such that jw 1 j, we can show that w 1
and w 2 must lead to different vertices in any deterministic realization, D, of RG(r; k).
Assume that w 1 and w 2 lead to the same vertex in D. Let c d (w) be the cost of string
w in D. Given any suffix s of length k \Gamma ', we can show that c(w 1
c d (w 1 The right hand side is a fixed value, \Delta.
Consider any position i - ' in which w 1 and w 2 differ. Denote the ith symbol of
string w by w(i). Consider two suffixes, s 1 and s 2 , of length
(i). Observe that the given weighting on RG(r; forces the
minimum cost path for any string with some symbol oe in position j to follow rail (r\Gammaoe).
Thus,
We can use this to show that c(w 1
6 Experimental Observations on ASR WFAs
To determine whether ASR WFAs manifest weight dependence, we experimented on
100 WFAs generated by the AT&T speech recognizer [23], using a grammar for the Air
Travel Information System (ATIS), a standard test bed [4]. Each transition was labeled
with a word and weighted by the recognizer with the negated log probability of realizing
that transition out of the source state; we refer to these weights as speech weights.
We determinized each WFA with its speech weights, with zero weights, and with
weights assigned independently and uniformly at random from [0; 2 i \Gamma1] Z (for each 0 -
could not be determinized with speech weights due to computational
limitations, and it is omitted from the data.

Figure

2(a) shows how many WFAs expanded when determinized with different
weightings. Figure 2(b) classifies the 63 WFAs that expanded with at least one weight-
ing. For each WFA, we took the weighting that produced maximal expansion. This was
usually the 8-bit random weighting, although due to computational limitations we were
unable to determinize some WFAs with large random weightings. The x-axis indicates
the open interval within which the value lg(jdta(G)j=jGj) falls.
The utility of determinization in ASR includes the reduction in size achieved with
actual speech weights. In our sample, 82 WFAs shrank when determinized. For each,
we computed the value lg(jGj=jdta(G)j), and we plot the results in Fig. 2(c).
In Fig. 2(d), we examine the relationship between the value lg(jdta(G)j=jGj) and
the number of bits used in random weights. We chose the ten WFAs with highest final
expansion value and plotted lg(jdta(G)j=jGj) against the number of bits used. For
reference the functions i
are plotted, where i is the number of bits. Most
speech zerosbit
rndbit
rndbit
rndbit
rndbit
rndbit
rndbit
rndbit
rnd
Type of weighting2060
Number
of
WFAs
that
expand
(a)
Log base 2 of expansion factor515
Number
of
WFAs
(b)
Log base 2 of shrinkage
Number
of
WFAs
(c)
Number of random bits26Log
of
expansion
factor
q0v004
(d)
Fig. 2. Observations on ASR WFAs.
of the WFAs exhibit subexponential growth as the number of bits increases, although
some, like q0t063 have increased by 128 times even with four random bits.
The WFA that could not be determinized with speech weights was "slightly hot,"
in that the determinized zero-weighted variant had 2.7% more arcs than the original
WFA. The remaining ninety-nine WFAs shrank with zero weights: none was hot. If one
expanded, it did so due to weights rather than topology.

Figure

2(a) indicates that many of the WFAs have some degree of weight dependence

Figure

2(d) suggests that random weights are a good way to estimate the degree
to which a WFA is weight dependent. Note that the expansion factor is some superlin-
possibly exponential, function of the number of random bits, suggesting that large,
e.g., 32-bit, random weights should cause expansion if anything will. Analogous experiments
on the minimized determinized WFAs yield results that are qualitatively the
same, although fewer WFAs still expand after minimization. Hence weight dependence
seems to be a fundamental property of these WFAs rather than an artifact of DTA.

Acknowledgements

. We thank Mehryar Mohri, Fernando Pereira, and Antonio Restivo
for fruitful discussions.


--R

Network Flows: Theory

Rational Series and Their Languages.

Algorithmic aspects in speech recognition: An intro- duction
Universal classes of hash functions.
Une caracterisation des fonctions sequentielles et des fonctions sous- sequentielles en tant que relations rationnelles

Finite automata computing real functions.

On computational power of weighted finite automata.

On measuring nondeterminism in regular languages.
Arithmetic coding of weighted finite automata.
Amounts of nondeterminism in finite automata.


On the use of sequential transducers in natural language processing.
Speech recognition by composition of weighted finite automata.
Weighted rational transductions and their application to human language processing.
Computational Geometry: An Introduction.
Probabilistic automata.
The AT&T
Analyse Syntaxique Transformationelle du Francais par Transducteurs et Lexique- Grammaire


Economy of description for single-valued transducers
--TR

--CTR
Mark G. Eramian, Efficient simulation of nondeterministic weighted finite automata, Journal of Automata, Languages and Combinatorics, v.9 n.2-3, p.257-267, September 2004
Bjrn Borchardt, A pumping lemma and decidability problems for recognizable tree series, Acta Cybernetica, v.16 n.4, p.509-544, 2004
Julien Quint, On the equivalence of weighted finite-state transducers, Proceedings of the ACL 2004 on Interactive poster and demonstration sessions, p.23-es, July 21-26, 2004, Barcelona, Spain
Manfred Droste , Dietrich Kuske, Skew and infinitary formal power series, Theoretical Computer Science, v.366 n.3, p.199-227, 20 November 2006
Bjrn Borchardt , Heiko Vogler, Determinization of finite state weighted tree automata, Journal of Automata, Languages and Combinatorics, v.8 n.3, p.417-463, 06/01/2003
Manfred Droste , Paul Gastin, Weighted automata and weighted logics, Theoretical Computer Science, v.380 n.1-2, p.69-86, June, 2007
Cyril Allauzen , Mehryar Mohri, Efficient algorithms for testing the twins property, Journal of Automata, Languages and Combinatorics, v.8 n.2, p.117-144, April
Ines Klimann , Sylvain Lombardy , Jean Mairesse , Christophe Prieur, Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton, Theoretical Computer Science, v.327 n.3, p.349-373, 2 November 2004
Sylvain Lombardy , Jacques Sakarovitch, Sequential?, Theoretical Computer Science, v.356 n.1, p.224-244, 5 May 2006
Manfred Droste , Heiko Vogler, Weighted tree automata and weighted logics, Theoretical Computer Science, v.366 n.3, p.228-247, 20 November 2006
rational functions and power series;algorithms;speech recognition;weighted automata