Difference: MinimizeDoc (13 vs. 14)

Revision 142019-02-24 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

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

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

Examples

Acceptor minimization

A B
minimize1.png minimize2.png

Minimize(A, &B);
fstminimize a.fst b.fst

Transducer minimization

A B
t-minimize1.png t-minimize2.png

Minimize(A, &B);
fstminimize a.fst b.fst

A B C
t-minimize1.png t-minimize3.png t-minimize4.png

Minimize(A, &B, &C);
fstminimize a.fst b.fst c.fst

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.
Deleted:
<
<
-- CyrilAllauzen - 27 Feb 2009
 
META FILEATTACHMENT attachment="minimize1.png" attr="" comment="Mimize example: input acceptor" date="1237320449" name="minimize1.png" path="minimize1.png" size="15468" stream="minimize1.png" tmpFilename="/var/tmp/CGItemp11490" user="CyrilAllauzen" version="2"
META FILEATTACHMENT attachment="minimize2.png" attr="" comment="Minimize example: output acceptor" date="1237320402" name="minimize2.png" path="minimize2.png" size="11111" stream="minimize2.png" tmpFilename="/var/tmp/CGItemp11424" user="CyrilAllauzen" version="2"
META FILEATTACHMENT attachment="t-minimize1.png" attr="" comment="Minimize example: transducer input" date="1281990666" name="t-minimize1.png" path="t-minimize1.png" size="17995" stream="t-minimize1.png" tmpFilename="/var/tmp/CGItemp29089" user="CyrilAllauzen" version="2"
META FILEATTACHMENT attachment="t-minimize2.png" attr="" comment="Minimize example: transducer output" date="1281990696" name="t-minimize2.png" path="t-minimize2.png" size="16155" stream="t-minimize2.png" tmpFilename="/var/tmp/CGItemp29234" user="CyrilAllauzen" version="2"
META FILEATTACHMENT attachment="t-minimize3.png" attr="" comment="Minimize example: transducer output 1" date="1282058255" name="t-minimize3.png" path="t-minimize3.png" size="14911" stream="t-minimize3.png" tmpFilename="/var/tmp/CGItemp25753" user="CyrilAllauzen" version="1"
META FILEATTACHMENT attachment="t-minimize4.png" attr="" comment="Minimize example: transducer output 2" date="1282058320" name="t-minimize4.png" path="t-minimize4.png" size="10994" stream="t-minimize4.png" tmpFilename="/var/tmp/CGItemp25808" user="CyrilAllauzen" version="1"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback