MinimizeDoc < FST

FST Web>FstQuickTour>MinimizeDoc (2019-02-24, MichaelRiley) (raw view)

---+ 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

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

---++ Examples

---+++ Acceptor minimization

|   ==A==    |  ==B==   |
| %ATTACHURL%/minimize1.png | %ATTACHURL%/minimize2.png |

<verbatim>
Minimize(A, &B);
fstminimize a.fst b.fst
</verbatim>


---+++ Transducer minimization

|   ==A==    |  ==B==   |
| %ATTACHURL%/t-minimize1.png | %ATTACHURL%/t-minimize2.png |

<verbatim>
Minimize(A, &B);
fstminimize a.fst b.fst
</verbatim>

|   ==A==    |  ==B==   |   ==C==   |
| %ATTACHURL%/t-minimize1.png | %ATTACHURL%/t-minimize3.png | %ATTACHURL%/t-minimize4.png |

<verbatim>
Minimize(A, &B, &C);
fstminimize a.fst b.fst c.fst
</verbatim>


---++ Complexity

=Minimize=
   * Time:
      * Acyclic: _O(E)_
      * Unweighted: _O(E log V)_
      * Weighted: complexity of [[ShortestDistanceDoc][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. [[http://www.cs.nyu.edu/~mohri/postscript/tcs.ps][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.

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
png	minimize1.png	r2 r1	manage	15.1 K	2009-03-17 - 20:07	CyrilAllauzen	Mimize example: input acceptor
png	minimize2.png	r2 r1	manage	10.9 K	2009-03-17 - 20:06	CyrilAllauzen	Minimize example: output acceptor
png	t-minimize1.png	r2 r1	manage	17.6 K	2010-08-16 - 20:31	CyrilAllauzen	Minimize example: transducer input
png	t-minimize2.png	r2 r1	manage	15.8 K	2010-08-16 - 20:31	CyrilAllauzen	Minimize example: transducer output
png	t-minimize3.png	r1	manage	14.6 K	2010-08-17 - 15:17	CyrilAllauzen	Minimize example: transducer output 1
png	t-minimize4.png	r1	manage	10.7 K	2010-08-17 - 15:18	CyrilAllauzen	Minimize example: transducer output 2

Topic revision: r14 - 2019-02-24 - MichaelRiley