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 Determinize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst); |
%DOX{namespacefst.html#Determinize[]}% |

template <class Arc> DeterminizeFst<Arc>:: DeterminizeFst(const Fst<Arc> &fst); |
%DOX{fst::DeterminizeFst[]}% |

fstdeterminize a.fst out.fst |

`A`

:

(TropicalWeight)

`Determinize of A`

:

Determinize(&A); DeterminizeFst<Arc>(A); fstdeterminize a.fst out.fst

`Determinize`

: - Determinizable:
*exponential (polynomial in the size of the output)* - Non-determinizable:
*does not terminate*

`DeterminizeFst:`

- Determinizable:
*exponential (polynomial in the size of the output)* - Non-determinizable:
*does not terminate*

The determinizable automata include all unweighted and all acyclic input.

Non-functional transducers can be handled by passing the 'disambiguate_output' option when the semiring has the path property (in a variant call to this function/class). In this case, only the shortest path output for each input is retained.

- Mehryar Mohri. Finite-State Transducers in Language and Speech Processing.
*Computational Linguistics*, 23:2, 1997. - Cyril Allauzen and Mehryar Mohri. Efficient Algorithms for Testing the Twins Property.
*Journal of Automata, Languages and Combinatorics*, 8(2):117-144, 2003.

-- MichaelRiley - 20 Jun 2007

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

jpg | determinize1.jpg | r2 r1 | manage | 12.5 K | 2007-06-21 - 21:43 | MichaelRiley | |

jpg | determinize2.jpg | r2 r1 | manage | 13.7 K | 2007-06-21 - 21:43 | MichaelRiley |

Topic revision: r13 - 2014-05-06 - 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