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);
|
[bad link?] |
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.
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 non-deterministic result even when the epsilons are treated as regular symbols. The
subsequential label can be chosen as a non-zero value to avoid this issue by passing it as an option (in a variant call to this function/class).
Non-functional transducers can be handled by passing the 'disambiguate_output' option when the semiring has the
path property (in a variant call to this function/class). In this case, only the shortest path output for each input is retained.
See Also
Disambiguate,
RmEpsilon
References
--
MichaelRiley - 20 Jun 2007