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.
See Also
Disambiguate,
RmEpsilon
References
--
MichaelRiley - 20 Jun 2007