TWiki
>
FST Web
>
FstQuickTour
>
DeterminizeDoc
(2019-02-24,
MichaelRiley
)
(raw view)
E
dit
A
ttach
---+ 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>| | |<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. ---++ 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 Non-functional transducers are handled by choosing he determinize type option (in a variant call to this function/class): * FUNCTIONAL: give an error for non-functional input (default) * NONFUNCTIONAL: permissible when the output ambiguity is finite (_p-subsequentiable_). The _subsequential_label_ should be non-zero and _increment_subsequential_label_ should be true or the result can be non-deterministic by the default use of epsilons as the p-subsequential labels found at the ends of paths. Care should be taken that these p-subsequential labels (_subsequential_label_, ..., _subsequential_label - p - 1_) do not collide with existing labels. * DISAMBIGUATE: only the shortest path output for each input is retained, permissible when the semiring has the [[FstWeightRequirements][path property]] ---++ See Also [[DisambiguateDoc][Disambiguate]], [[RmEpsilonDoc][RmEpsilon]] ---++ 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.
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
E
dit
|
A
ttach
|
Watch
|
P
rint version
|
H
istory
: r16
<
r15
<
r14
<
r13
<
r12
|
B
acklinks
|
V
iew topic
|
WYSIWYG
|
M
ore topic actions
Topic revision: r16 - 2019-02-24
-
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