RmEpsilon

Description

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.

Usage

template <class Arc>
void RmEpsilon(MutableFst<Arc> *fst); 
doc
template <class Arc> RmEpsilonFst<Arc>::
RmEpsilonFst(const Fst<Arc>& fst);
doc
fstrmepsilon [--opts] a.fst out.fst
 --connect: Trim output (def: true)
 

Examples

A:

rmepsilon1.jpg

(TropicalWeight)

RmEpsilon of A:

rmepsilon2.jpg

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

Complexity

RmEpsilon:
  • TIme:
    • Unweighted: O(V2 + V E)
    • Acyclic: O(V2 + V E)
    • Tropical semiring: O(V2 log V + V E)
    • General: exponential
  • Space: O(V E)
where V = # of states and E = # of arcs.

RmEpsilonFst:

  • TIme:
    • Unweighted: O(v2 + v e)
    • General: exponential
  • 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.

Caveats

See here for a discussion on efficient usage.

References

-- CyrilAllauzen - 25 Jun 2007

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg rmepsilon1.jpg r1 manage 15.3 K 2007-07-02 - 20:25 MichaelRiley  
Unknown file formatfst rmepsilon2.fst r1 manage 0.1 K 2007-07-02 - 20:26 MichaelRiley  
JPEGjpg rmepsilon2.jpg r1 manage 9.0 K 2007-07-02 - 20:27 MichaelRiley  
Topic revision: r13 - 2012-05-13 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback