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);
template <class Arc> RmEpsilonFst<Arc>:: RmEpsilonFst(const Fst<Arc>& fst);
fstrmepsilon [--opts] a.fst out.fst --connect: Trim output (def: true)

Examples

A:

(TropicalWeight)

RmEpsilon of A:

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

Complexity

RmEpsilon:

• TIme:
  • Unweighted: O(V² + V E)
  • Acyclic: O(V² + V E)
  • Tropical semiring: O(V² log V + V E)
  • General: exponential
• Space: O(V E)

where V = # of states and E = # of arcs.

RmEpsilonFst:

• TIme:
  • Unweighted: O(v² + 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

• Mehryar Mohri. Generic Epsilon-Removal and Input Epsilon-Normalization Algorithms for Weighted Transducers, International Journal of Computer Science, 13(1):129-143 (2002).

-- CyrilAllauzen - 25 Jun 2007