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.

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

This topic: FST > WebHome > FstQuickTour > DeterminizeDoc

Topic revision: r12 - 2014-04-23 - MichaelRiley

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