Determinize

Description

This operation determinizes a weighted transducer. The result will be an equivalent FST that has the property that no state has two transitions with the same input label. For this algorithm, epsilon transitions are treated as regular symbols (cf. RmEpsilon).

The transducer must be functional. The weights must be (weakly) left divisible (valid for TropicalWeight and LogWeight for instance) and zero-sum-free.

Usage

template <class Arc> void Determinize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);
template <class Arc> DeterminizeFst<Arc>:: DeterminizeFst(const Fst<Arc> &fst);
fstdeterminize a.fst out.fst

Examples

A:

(TropicalWeight)

Determinize of A:

Determinize(&A);
DeterminizeFst<Arc>(A);
fstdeterminize a.fst out.fst

Complexity

Determinize:

• Determinizable: exponential (polynomial in the size of the output)
• Non-determinizable: does not terminate

DeterminizeFst:

• Determinizable: exponential (polynomial in the size of the output)
• Non-determinizable: does not terminate

The determinizable automata include all unweighted and all acyclic input.

References

• Mehryar Mohri. Finite-State Transducers in Language and Speech Processing. Computational Linguistics, 23:2, 1997.
• Cyril Allauzen and Mehryar Mohri. Efficient Algorithms for Testing the Twins Property. Journal of Automata, Languages and Combinatorics, 8(2):117-144, 2003.

-- MichaelRiley - 20 Jun 2007