(r8) DeterminizeDoc < FST

FST Web>FstQuickTour>DeterminizeDoc (revision 8) (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, [[FstGlossary#EpsilonDef][epsilon]] transitions are treated as regular symbols (cf. [[RmEpsilonDoc][RmEpsilon]]).


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

---++ Usage
|<verbatim>
template <class Arc>
void Determinize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);
</verbatim>| %DOX{namespacefst.html#Determinize[%H%]}% |
|<verbatim>
template <class Arc> DeterminizeFst<Arc>::
DeterminizeFst(const Fst<Arc> &fst);
</verbatim>| %DOX{fst::DeterminizeFst[%H%]}% |
|<verbatim>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:=
   * 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.
     [[http://www.cs.nyu.edu/~mohri/postscript/cl1.pdf][Finite-State Transducers in Language and Speech Processing.]]
     _Computational Linguistics_, 23:2, 1997.
   * Cyril Allauzen and Mehryar Mohri.
     [[http://cs.nyu.edu/~allauzen/pdf/twins.pdf][Efficient Algorithms for Testing the Twins Property.]]
     _Journal of Automata, Languages and Combinatorics_, 8(2):117-144, 2003.

-- 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-21 - 21:43	MichaelRiley
jpg	determinize2.jpg	r2 r1	manage	13.7 K	2007-06-21 - 21:43	MichaelRiley

Topic revision: r8 - 2009-03-03 - MichaelRiley