Minimize
This operation performs the minimization of deterministic weighted automata and transducers.
Description
Usage
Examples
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
A
.
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