(r1) DeterminizeDoc < FST

FST Web>FstQuickTour>DeterminizeDoc (revision 1) (raw view)~~EditAttach~~

---+ Determinize

---++ Description
This operation determinizes a weighted transducer.  The result will be
an [[FstGlossary#EquivalentDef][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. [[RmEpsilonDoc][RmEpsilon]]).


The transducer must be [[FstGlossary#FunctionalDef][functional]]. The weights must be (weakly)
[[FstWeights][left divisible]] (valid for !TropicalWeight and !LogWeight).

---++ Usage
<verbatim>
template <class Arc>
void Determinize(MutableFst<Arc> *fst);

template <class Arc> DeterminizeFst<Arc>::
DeterminizeFst(const Fst<Arc> &fst);

fstdeterminize a.fst out.fst
</verbatim>

---++ Examples

---+++ =A=:

%ATTACHURL%/determinize1.jpg

---+++ =Determinize of A=:

%ATTACHURL%/determinize2.jpg

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

---++ Complexity
=Determinize=:
   * determinizable: _exponential (polynomial in the size of the output)_
   * non-determinizable: _does not terminate_
=DeterminizeFst:=
   * Constructor: _O(1)_
   * Traversal: 
      * determinizable: _exponential (polynomial in the size of the output)_
      * non-determinizable: _does not terminate_

The determinizable automata include all unweighted and all acyclic input.

-- Main.MichaelRiley - 20 Jun 2007

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
jpg	determinize1.jpg	r2 r1	manage	12.5 K	2007-06-20 - 16:38	MichaelRiley
jpg	determinize2.jpg	r2 r1	manage	13.7 K	2007-06-20 - 16:38	MichaelRiley

Topic revision: r1 - 2007-06-20 - MichaelRiley