TWiki
>
FST Web
>
FstQuickTour
>
DeterminizeDoc
(revision 11) (raw view)
Edit
Attach
---+ 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 for instance) and [[FstGlossary#ZeroSumFreeDef][zero-sum-free]]. ---++ 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 (!TropicalWeight) ---+++ =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
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
Edit
|
Attach
|
Watch
|
P
rint version
|
H
istory
:
r16
|
r13
<
r12
<
r11
<
r10
|
B
acklinks
|
V
iew topic
|
Raw edit
|
More topic actions...
Topic revision: r11 - 2014-04-23
-
MichaelRiley
FST
Log In
or
Register
FST Web
Create New Topic
Index
Search
Changes
Notifications
Statistics
Preferences
Webs
Contrib
FST
Forum
GRM
Kernel
Main
Sandbox
TWiki
Main
Copyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback