TWiki> FST Web>FstQuickTour>MinimizeDoc (revision 5)EditAttach

Minimize

Description

Work in progress, under construction This operation performs the minimization of deterministic weighted automata and transducers.

Usage

template<class Arc>
void Minimize(MutableFst<Arc> *fst, MutableFst<Arc> *sfst = 0);
doc [bad link?]
fstminimize  in.fst [out1.fst [out2.fst]]

Examples

Work in progress, under construction 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

Edit | Attach | Watch | Print version | History: r14 | r7 < r6 < r5 < r4 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r5 - 2009-03-03 - CyrilAllauzen
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback