Difference: RmEpsilonDoc (1 vs. 14)

Revision 142018-04-27 - MichaelRiley

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

RmEpsilon

Line: 11 to 11
 |
template <class Arc>
void RmEpsilon(MutableFst<Arc> *fst); 
Changed:
<
<
| %DOX{namespacefst.html#RmEpsilon[doc]}% |
>
>
| |
 |
template <class Arc> RmEpsilonFst<Arc>::
RmEpsilonFst(const Fst<Arc>& fst);

Revision 132012-05-13 - MichaelRiley

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

RmEpsilon

Line: 56 to 56
 where v = # of states visited, e = # of arcs visited. Constant time to visit an input state or arc is assumed and exclusive of caching.
Added:
>
>

Caveats

See here for a discussion on efficient usage.

 

References

Revision 122011-12-06 - MichaelRiley

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

RmEpsilon

Line: 27 to 27
 

A:

rmepsilon1.jpg
Added:
>
>
(TropicalWeight)
 

RmEpsilon of A:

rmepsilon2.jpg

Revision 112009-04-30 - CyrilAllauzen

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

RmEpsilon

Line: 25 to 25
 

Examples

A:

Changed:
<
<
/twiki/pub/FST/RmEpsilonDoc/rmepsilon1.jpg
>
>
rmepsilon1.jpg
 

RmEpsilon of A:

Changed:
<
<
/twiki/pub/FST/RmEpsilonDoc/rmepsilon2.jpg
>
>
rmepsilon2.jpg
 
RmEpsilon(&A);

Revision 102009-03-06 - CyrilAllauzen

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

RmEpsilon

Line: 52 to 52
 
    • General: exponential
  • Space: O(v e)
where v = # of states visited, e = # of arcs visited.
Changed:
<
<
Constant time to visit an input state or arc is assumed and exclusive of caching.
>
>
Constant time to visit an input state or arc is assumed and exclusive of caching.
 

References

  • Mehryar Mohri.

Revision 92007-07-05 - CyrilAllauzen

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

RmEpsilon

Line: 37 to 37
 

Complexity

Changed:
<
<
RmEpsilon:
>
>
RmEpsilon:
 
  • TIme:
    • Unweighted: O(V2 + V E)
    • Acyclic: O(V2 + V E)
Line: 46 to 46
 
  • Space: O(V E)
where V = # of states and E = # of arcs.
Changed:
<
<
RmEpsilonFst:
>
>
RmEpsilonFst:
 
  • TIme:
    • Unweighted: O(v2 + v e)
    • General: exponential

Revision 82007-07-03 - MichaelRiley

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

RmEpsilon

Description

Changed:
<
<
This operation removes epsilon-transitions (when both input and output labels are epsilons) from a transducer. The result will be an equivalent FST that has no such epsilon
>
>
This operation removes epsilon-transitions (when both the input and output label are an epsilon) from a transducer. The result will be an equivalent FST that has no such epsilon
 transitions.

Revision 72007-07-02 - MichaelRiley

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

RmEpsilon

Description

Changed:
<
<
This operation removes epsilon-transitions (both input and output labels are epsilons) in a transducer. The result will be an equivalent FST that has no epsilon transition.
>
>
This operation removes epsilon-transitions (when both input and output labels are epsilons) from a transducer. The result will be an equivalent FST that has no such epsilon transitions.
 

Usage

Line: 63 to 63
 
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183407982" name="rmepsilon2.fst" path="rmepsilon2.fst" size="109" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183407950" name="rmepsilon1.jpg" path="rmepsilon1.jpg" size="15694" user="Main.MichaelRiley" version="1"
Changed:
<
<
META FILEATTACHMENT attachment="rmepsilon2.jpg" attr="" comment="" date="1183408041" name="rmepsilon2.jpg" path="rmepsilon2.jpg" size="9259" stream="rmepsilon2.jpg" user="Main.MichaelRiley" version="1"
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183408044" name="rmepsilon2.jpg" path="rmepsilon2.jpg" size="9259" user="Main.MichaelRiley" version="1"

Revision 62007-07-02 - MichaelRiley

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

RmEpsilon

Line: 60 to 60
  International Journal of Computer Science, 13(1):129-143 (2002).

-- CyrilAllauzen - 25 Jun 2007 \ No newline at end of file

Added:
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183407982" name="rmepsilon2.fst" path="rmepsilon2.fst" size="109" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183407950" name="rmepsilon1.jpg" path="rmepsilon1.jpg" size="15694" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attachment="rmepsilon2.jpg" attr="" comment="" date="1183408041" name="rmepsilon2.jpg" path="rmepsilon2.jpg" size="9259" stream="rmepsilon2.jpg" user="Main.MichaelRiley" version="1"

Revision 52007-07-02 - MichaelRiley

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

RmEpsilon

Revision 42007-07-02 - MichaelRiley

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

RmEpsilon

Line: 17 to 17
 RmEpsilonFst(const Fst& fst); | %DOX{fst::RmEpsilonFst[doc]}% | |
Changed:
<
<
fstrmepsilon a.fst out.fst -connect: Trim output (def: true)
>
>
fstrmepsilon [--opts] a.fst out.fst --connect: Trim output (def: true)
  | |
Line: 38 to 38
 

Complexity

RmEpsilon:
Changed:
<
<
  • Unweighted: O(nstates^2 + nstates * narcs)
  • Acyclic: O(nstates^2 + nstates * narcs)
  • Tropical semiring: O(nstates^2 * log(nstates) + nstates * narcs)
>
>
  • TIme:
    • Unweighted: O(V2 + V E)
    • Acyclic: O(V2 + V E)
    • Tropical semiring: O(V2 log V + V E)
 
  • General: exponential
Added:
>
>
  • Space: O(V E)
where V = # of states and E = # of arcs.
 RmEpsilonFst:
Changed:
<
<
  • Constructor: O(1)
  • Traversal:
    • Unweighted: O(nstates^2 + nstates * narcs)
>
>
  • TIme:
    • Unweighted: O(v2 + v e)
 
    • General: exponential
Changed:
<
<
Space complexity: O(nstates * narcs)
>
>
  • Space: O(v e)
where v = # of states visited, e = # of arcs visited. Constant time to visit an input state or arc is assumed and exclusive of caching.
 

References

  • Mehryar Mohri.

Revision 32007-06-26 - MichaelRiley

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

RmEpsilon

Line: 10 to 10
 

Usage

|
template <class Arc>
Changed:
<
<
void RmEpsilon(MutableFst *fst, bool connect = true); | %DOX{namespacefst.html#RmEpsilon[Help]}% |
>
>
void RmEpsilon(MutableFst *fst); | %DOX{namespacefst.html#RmEpsilon[doc]}% |
 |
template <class Arc> RmEpsilonFst<Arc>::
RmEpsilonFst(const Fst<Arc>& fst);
Changed:
<
<
| %DOX{fst::RmEpsilonFst[Help]}% |
 fstrmepsilon a.fst out.fst 
 
>
>
| %DOX{fst::RmEpsilonFst[doc]}% |
fstrmepsilon a.fst out.fst
 -connect: Trim output (def: true)
 
 

Examples

Revision 22007-06-25 - CyrilAllauzen

Line: 1 to 1
Changed:
<
<
META TOPICPARENT name="DeterminizeDoc"
>
>
META TOPICPARENT name="FstQuickTour"
 

RmEpsilon

Added:
>
>

Description

This operation removes epsilon-transitions (both input and output labels are epsilons) in a transducer. The result will be an equivalent FST that has no epsilon transition.
 
Changed:
<
<
-- MichaelRiley - 20 Jun 2007
>
>

Usage

template <class Arc>
void RmEpsilon(MutableFst<Arc> *fst, bool connect = true); 
%DOX{namespacefst.html#RmEpsilon[Help]}%
template <class Arc> RmEpsilonFst<Arc>::
RmEpsilonFst(const Fst<Arc>& fst);
%DOX{fst::RmEpsilonFst[Help]}%
 fstrmepsilon a.fst out.fst 
 

Examples

A:

/twiki/pub/FST/RmEpsilonDoc/rmepsilon1.jpg

RmEpsilon of A:

/twiki/pub/FST/RmEpsilonDoc/rmepsilon2.jpg

RmEpsilon(&A);
RmEpsilonFst<Arc>(A);
fstrmepsilon a.fst out.fst

Complexity

RmEpsilon:
  • Unweighted: O(nstates^2 + nstates * narcs)
  • Acyclic: O(nstates^2 + nstates * narcs)
  • Tropical semiring: O(nstates^2 * log(nstates) + nstates * narcs)
  • General: exponential
RmEpsilonFst:
  • Constructor: O(1)
  • Traversal:
    • Unweighted: O(nstates^2 + nstates * narcs)
    • General: exponential
Space complexity: O(nstates * narcs)

References

-- CyrilAllauzen - 25 Jun 2007

Revision 12007-06-20 - MichaelRiley

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

RmEpsilon

-- MichaelRiley - 20 Jun 2007

 
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