rm_epsilon.md

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);

RmEpsilonFst

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^2 + V E)$

• Acyclic: $O(V^2 + V E)$

• Tropical semiring: $O(V^2 \log V + V E)$

• General: exponential

• Space: $O(V E)$

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

RmEpsilonFst:

• TIme:

• Unweighted: $O(v^2 + 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).