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

RmEpsilon

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.

Usage

template <class Arc>
void RmEpsilon(MutableFst<Arc> *fst, bool connect = true); 
Help [bad link?]
template <class Arc> RmEpsilonFst<Arc>::
RmEpsilonFst(const Fst<Arc>& fst);
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

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