Difference: MinimizeDoc (1 vs. 14)

Revision 142019-02-24 - MichaelRiley

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

Minimize

Line: 68 to 68
 
  • 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"

Revision 132018-04-27 - MichaelRiley

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

Minimize

Line: 16 to 16
 |
template<class Arc>
void Minimize(MutableFst<Arc> *fst, MutableFst<Arc> *sfst = nullptr, float delta = kDelta, bool allow_nondet = false);
Changed:
<
<
| %DOX{namespacefst.html#Minimize[doc]}% |
>
>
|
 |
fstminimize  in.fst [out1.fst [out2.fst]]
Changed:
<
<
||
>
>
|
 

Examples

Revision 122017-02-03 - KyleGorman

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

Minimize

Line: 15 to 15
  |
template<class Arc>
Changed:
<
<
void Minimize(MutableFst *fst, MutableFst *sfst = 0);
>
>
void Minimize(MutableFst *fst, MutableFst *sfst = nullptr, float delta = kDelta, bool allow_nondet = false);
  | %DOX{namespacefst.html#Minimize[doc]}% | |
fstminimize  in.fst [out1.fst [out2.fst]]

Revision 112010-08-17 - CyrilAllauzen

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

Minimize

Line: 36 to 36
 

Transducer minimization

Deleted:
<
<
Work in progress, under construction TBA
 
A B
t-minimize1.png t-minimize2.png
Line: 46 to 44
 fstminimize a.fst b.fst
Deleted:
<
<
Work in progress, under construction TBA
 
A B C
t-minimize1.png t-minimize3.png t-minimize4.png
Line: 78 to 74
 
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"
Added:
>
>
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"

Revision 102010-08-16 - CyrilAllauzen

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

Minimize

Line: 39 to 39
 Work in progress, under construction TBA

A B
Changed:
<
<
minimize3.png minimize4.png
>
>
t-minimize1.png t-minimize2.png
 
Minimize(A, &B);
Line: 49 to 49
 Work in progress, under construction TBA

A B C
Changed:
<
<
minimize3.png minimize5.png minimize6.png
>
>
t-minimize1.png t-minimize3.png t-minimize4.png
 
Minimize(A, &B, &C);
Line: 76 to 76
 
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"
Added:
>
>
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"

Revision 92009-03-27 - CyrilAllauzen

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

Minimize

Line: 25 to 25
 

Acceptor minimization

Changed:
<
<

A:

>
>
A B
minimize1.png minimize2.png
 
Changed:
<
<
minimize1.png
>
>
Minimize(A, &B);
fstminimize a.fst b.fst
 
Deleted:
<
<

B:

 
Changed:
<
<
minimize2.png
>
>

Transducer minimization

 
Added:
>
>
Work in progress, under construction TBA
 
A B
Changed:
<
<
minimize1.png minimize2.png
>
>
minimize3.png minimize4.png
 
Minimize(A, &B);
Line: 43 to 46
 fstminimize a.fst b.fst
Added:
>
>
Work in progress, under construction TBA
 
Changed:
<
<

Transducer minimization

>
>
A B C
minimize3.png minimize5.png minimize6.png

Minimize(A, &B, &C);
fstminimize a.fst b.fst c.fst
 
Deleted:
<
<
Work in progress, under construction TBA
 

Complexity

Revision 82009-03-18 - CyrilAllauzen

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

Minimize

Line: 9 to 9
 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.
Changed:
<
<
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. 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 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.
>
>
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

Revision 72009-03-18 - CyrilAllauzen

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

Minimize

Line: 9 to 9
 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.
Changed:
<
<
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. 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 transducer with each strings that is the output label 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.
>
>
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. 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 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

Revision 62009-03-17 - CyrilAllauzen

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

Minimize

Description

Changed:
<
<
Work in progress, under construction This operation performs the minimization of deterministic weighted automata and transducers.
>
>
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. 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 transducer with each strings that is the output label 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

Line: 18 to 23
 

Examples

Added:
>
>

Acceptor minimization

A:

minimize1.png

B:

minimize2.png

A B
minimize1.png minimize2.png

Minimize(A, &B);

fstminimize a.fst b.fst

Transducer minimization

 Work in progress, under construction TBA

Complexity

Line: 36 to 64
 
  • Dominique Revuz. Minimisation of Acyclic Deterministic Automata in Linear Time. Theoretical Computer Science, 92(1): 181-189, 1992.

-- CyrilAllauzen - 27 Feb 2009

Added:
>
>
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"

Revision 52009-03-03 - CyrilAllauzen

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

Minimize

Line: 10 to 10
  |
template<class Arc>
Changed:
<
<
Minimize(MutableFst *fst, MutableFst *sfst = 0);
>
>
void Minimize(MutableFst *fst, MutableFst *sfst = 0);
  | %DOX{namespacefst.html#Minimize[doc]}% | |
fstminimize  in.fst [out1.fst [out2.fst]]
Line: 27 to 27
 
    • Acyclic: O(E)
    • Unweighted: O(E log V)
    • Weighted: complexity of shortest distance + complexity of unweighted minimization
Changed:
<
<
where V = # of states and E = # of transitions in the input Fst A.
>
>
where V = # of states and E = # of transitions in the input Fst.
 

References

Revision 42009-03-02 - CyrilAllauzen

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

Minimize

Description

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

Usage

Line: 18 to 18
 

Examples

Changed:
<
<
TBA
>
>
Work in progress, under construction TBA
 

Complexity

Revision 32009-03-02 - CyrilAllauzen

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

Minimize

Deleted:
<
<
This operation performs the minimization of deterministic weighted automata and transducers.
 

Description

Changed:
<
<
>
>
This operation performs the minimization of deterministic weighted automata and transducers.
 

Usage

Added:
>
>
template<class Arc>
Minimize(MutableFst<Arc> *fst, MutableFst<Arc> *sfst = 0);
%DOX{namespacefst.html#Minimize[doc]}%
fstminimize  in.fst [out1.fst [out2.fst]]
 

Examples

Added:
>
>
TBA
 

Complexity

Minimize

Revision 22009-03-02 - CyrilAllauzen

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

Minimize

Line: 18 to 18
 Minimize
  • Time:
    • Acyclic: O(E)
Changed:
<
<
    • Unweighted: O(E log N)
>
>
    • Unweighted: O(E log V)
 
Added:
>
>
where V = # of states and E = # of transitions in the input Fst A.
 

References

Revision 12009-02-27 - CyrilAllauzen

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

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 N)
    • Weighted: complexity of shortest distance + complexity of unweighted minimization

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

 
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