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
zerosumfree.
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)
 Nondeterminizable: does not terminate
DeterminizeFst:
 Determinizable: exponential (polynomial in the size of the output)
 Nondeterminizable: does not terminate
The determinizable automata include all unweighted and all acyclic input.
Caveats
Epsilons may be added as input labels at the ends of paths when determinizing transducers. If input transducer also contains epsilons, this may result in a nondeterministic result even when the epsilons are treated as regular symbols. The
subsequential label can be chosen as a nonzero value to avoid this issue by passing it as an option
Nonfunctional transducers are handled by choosing he determinize type option (in a variant call to this function/class):
 FUNCTIONAL: give an error for nonfunctional input (default)
 NONFUNCTIONAL: permissible when the output ambiguity is finite (psubsequentiable). The subsequential_label should be nonzero and increment_subsequential_label should be true or the result can be nondeterministic by the default use of epsilons as the psubsequential labels found at the ends of paths. Care should be taken that these psubsequential labels (subsequential_label, ..., subsequential_label  p  1) do not collide with existing labels.
 DISAMBIGUATE: only the shortest path output for each input is retained, permissible when the semiring has the path property
See Also
Disambiguate, RmEpsilon
References