(r6) DisambiguateDoc < FST

FST Web>FstQuickTour>DisambiguateDoc (revision 6) (raw view)~~EditAttach~~

---+ Disambiguate 

---++ Description
This operation disambiguates a weighted transducer.  The result will be
an [[FstGlossary#EquivalentDef][equivalent]] FST that has the property
that no two successful paths have the same input labeling.
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 Disambiguate(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);
</verbatim>| %DOX{namespacefst.html#Determinize[%H%]}% |

---++ Examples

---+++ =A=:

%ATTACHURL%/disamb1.jpg

 (!TropicalWeight)

---+++ =Disambiguate of A=:

%ATTACHURL%/disamb2.jpg

<verbatim>
Disambiguate(A, &out);
fstdisambiguate a.fst out.fst
</verbatim>

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

%ATTACHURL%/disamb3.jpg

(For comparison since [[FstGlossary#DeterministicDef][deterministic]] implies [[FstGlossary#UnambiguousDef][unambiguous]].)

---++ Complexity
=Disambiguate=:
   * Disambiguate: _exponential (polynomial in the size of the output)_
   * Non-disambiguable: _does not terminate_

The disambiguable automata include all unweighted, all acyclic and all determinizable input. There are disambiguable automata that are not determinizable.

---++ See Also

[[DeterminizeDoc][Determinize]], [[RmEpsilonDoc][RmEpsilon]]


---++ References

   * Mehryar Mohri and Michael Riley,
     [[http://arxiv.org/abs/1405.0500][On the Disambiguation of Weighted Automata]],
     _ArXiv e-prints_, cs-FL/1405.0500, 2014.

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who
jpg	disamb1.jpg	r2 r1	manage	16.0 K	2014-04-22 - 23:25	MichaelRiley
jpg	disamb2.jpg	r1	manage	12.8 K	2014-04-22 - 23:26	MichaelRiley
jpg	disamb3.jpg	r1	manage	25.3 K	2014-04-22 - 23:27	MichaelRiley

Topic revision: r6 - 2014-05-20 - MichaelRiley