Disambiguate

Description

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.

Usage

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

Examples

A:

disamb1.jpg

(TropicalWeight)

Disambiguate of A:

disamb2.jpg

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

Determinize of A:

disamb3.jpg

(For comparison since deterministic implies 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

Determinize, RmEpsilon

References

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 | WYSIWYG | More topic actions
Topic revision: r7 - 2018-04-27 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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