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

`A`

:

(TropicalWeight)

`Disambiguate of A`

:

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

`Determinize of A`

:

(For comparison since deterministic implies unambiguous.)

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

- Mehryar Mohri and Michael Riley, On the Disambiguation of Weighted Automata,
*ArXiv e-prints*, cs-FL/1405.0500, 2014.

I | Attachment | History | Action | Size | Date | Who | Comment |
---|---|---|---|---|---|---|---|

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 |

This topic: FST > WebHome > FstQuickTour > DisambiguateDoc

Topic revision: r7 - 2018-04-27 - MichaelRiley

Copyright © 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

Ideas, requests, problems regarding TWiki? Send feedback