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

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

Edit | Attach | Watch | Print version | History: r14 | r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r2 - 2009-03-02 - 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