FST Web>FstQuickTour>DisambiguateDoc (2018-04-27, MichaelRiley)

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);

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

Examples

`A`:

(TropicalWeight)

`Disambiguate of A`:

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

`Determinize of A`:

(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.

References

Mehryar Mohri and Michael Riley, 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: r7 - 2018-04-27 - MichaelRiley