Minimize

Description

This operation performs the minimization of deterministic weighted automata and transducers.

If the input FST A is an automaton (acceptor), this operation produces the minimal automaton B equivalent to A, i.e. the automata with a minimal number of states that is equivalent to A.

If the input FST A is a transducer, this operation internally builds an equivalent transducer with a minimal number of states. However, this minimality is obtained by allowing transition having strings of symbols as output labels, this known in the litterature as a real-time transducer. Such transducers are not directly supported by the library. By defaut, Minimize will convert such transducer by expanding each string-labeled transition into a sequence of transitions. This will results in the creation of new states, hence losing the minimality property. If a second output argument is given to Minimize, then the first output B will be the minimal real-time transducer with each strings that is the output label of a transition being mapped to a new output symbol, the second output transducer C represents the mapping between new output labels and old output labels. Hence, we will have that A is equivalent to B o C.

Usage

template<class Arc>
void Minimize(MutableFst<Arc> *fst, MutableFst<Arc> *sfst = nullptr, float delta = kDelta, bool allow_nondet = false);
doc
fstminimize  in.fst [out1.fst [out2.fst]]

Examples

Acceptor minimization

A B
minimize1.png minimize2.png

Minimize(A, &B);
fstminimize a.fst b.fst

Transducer minimization

A B
t-minimize1.png t-minimize2.png

Minimize(A, &B);
fstminimize a.fst b.fst

A B C
t-minimize1.png t-minimize3.png t-minimize4.png

Minimize(A, &B, &C);
fstminimize a.fst b.fst c.fst

Complexity

Minimize

  • Time:
    • Acyclic: O(E)
    • Unweighted: O(E log V)
    • Weighted: complexity of shortest distance + complexity of unweighted minimization
where V = # of states and E = # of transitions in the input Fst.

References

  • John E. Hopcroft. An n log n algorithm for minimizing the states in a finite automaton. In Z. Kohavi, editor, The Theory of Machines and Computations, pages 189-196. Academic Press, 1971.
  • Mehryar Mohri. Minimization algorithms for sequential transducers. Theoretical Computer Science, 234(1-2): 177-201, 2000.
  • Dominique Revuz. Minimisation of Acyclic Deterministic Automata in Linear Time. Theoretical Computer Science, 92(1): 181-189, 1992.

-- CyrilAllauzen - 27 Feb 2009

Topic attachments
I Attachment History Action Size Date Who Comment
PNGpng minimize1.png r2 r1 manage 15.1 K 2009-03-17 - 20:07 CyrilAllauzen Mimize example: input acceptor
PNGpng minimize2.png r2 r1 manage 10.9 K 2009-03-17 - 20:06 CyrilAllauzen Minimize example: output acceptor
PNGpng t-minimize1.png r2 r1 manage 17.6 K 2010-08-16 - 20:31 CyrilAllauzen Minimize example: transducer input
PNGpng t-minimize2.png r2 r1 manage 15.8 K 2010-08-16 - 20:31 CyrilAllauzen Minimize example: transducer output
PNGpng t-minimize3.png r1 manage 14.6 K 2010-08-17 - 15:17 CyrilAllauzen Minimize example: transducer output 1
PNGpng t-minimize4.png r1 manage 10.7 K 2010-08-17 - 15:18 CyrilAllauzen Minimize example: transducer output 2
Topic revision: r12 - 2017-02-03 - KyleGorman
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback