Minimize
Description
This operation performs the minimization of deterministic weighted automata and transducers.
Usage
template<class Arc>
void Minimize(MutableFst<Arc> *fst, MutableFst<Arc> *sfst = 0);
|
[bad link?] |
fstminimize in.fst [out1.fst [out2.fst]]
|
Examples
TBA
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