** Next:** Subsequentiality and Bi-machines
** Up:** Future Work
** Previous:** Future Work

##

Minimization

The minimization algorithm for transducers [25,27]
can be applied to a bounded qpfst without modifications. The
transducer minimization algorithm consists of two steps. In the first
step, all output symbols are moved into preceding transitions as much
as is possible. This is done by computing for each state the longest
common prefix of the outputs associated with all paths from that state
to a final state. The second step of the transducer minimization
algorithm consists of the application of ordinary recognizer
minimization to the resulting transducer, temporarily treating the
labels as atomic symbols.

The application of the transducer minimization algorithm to a bounded
qfst might result in a qpfst with identities in which the output has
to be produced before the corresponding input symbol has been
observed. The queue-mechanism can be generalized to treat such cases
as well. We use an implementation of queues described in [33, page
299] in which an element can be dequeued before it is
enqueued. The output is a variable temporarily; obviously this
requires output to be buffered. We implemented this both in ` C++`
as well as in Prolog.

However, applying the transducer minimization algorithm in this way
does not neccessarily produce a minimal qpfst. One problem is that in
the transducer minimization algorithm, the final step consists of an
application of the recognizer minimization algorithm in such a way
that the labels of the transducer are temporarily treated as
unanalyzable atoms. This works in the case of ordinary transducers,
but is not good enough for our purposes. The following example
illustrates this particular problem.

The transduction implemented by this transducer is simply the
identity relation over . However, the application of the transducer
minimization algorithm will produce an identical transducer, rather
than the minimal one.

In the implementation in the Fsa Utilities we have constructed a
variety of heuristics, which includes a generalization of the
transducer minimization algorithm, in order to reduce the size of
deterministic transducers. In most practical cases, the heuristics
produce a minimal transducer.

** Next:** Subsequentiality and Bi-machines
** Up:** Future Work
** Previous:** Future Work
*Noord G.J.M. van*

*2001-06-22*