TWiki> FST Web>FstQuickTour>DisambiguateDoc (revision 4)EditAttach

Disambiguate Work in progress, under construction


This operation disambiguates a weighted transducer. The result will be an equivalent FST that has the property that no two successful paths have the same input labeling. For this algorithm, epsilon transitions are treated as regular symbols (cf. RmEpsilon).

The transducer must be functional. The weights must be (weakly) left divisible (valid for TropicalWeight and LogWeight for instance) and zero-sum-free.


template <class Arc>
void Disambiguate(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);





Disambiguate of A:


Disambiguate(A, &out);
fstdisambiguate a.fst out.fst

Determinize of A:


(For comparison since deterministic implies unambiguous.)


  • 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

Determinize, RmEpsilon


Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg disamb1.jpg r2 r1 manage 16.0 K 2014-04-22 - 23:25 MichaelRiley  
JPEGjpg disamb2.jpg r1 manage 12.8 K 2014-04-22 - 23:26 MichaelRiley  
JPEGjpg disamb3.jpg r1 manage 25.3 K 2014-04-22 - 23:27 MichaelRiley  
Edit | Attach | Watch | Print version | History: r7 < r6 < r5 < r4 < r3 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r4 - 2014-04-23 - MichaelRiley
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback