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 are handled by choosing he determinize type option (in a variant call to this function/class):

- FUNCTIONAL: give an error for non-functional input (default)
- NONFUNCTIONAL: permissible when the output ambiguity is finite (
*p-subsequentiable*). The*subsequential_label*should be non-zero and*increment_subsequential_label*should be true or the result can be non-deterministic by the default use of epsilons as the p-subsequential labels found at the ends of paths. Care should be taken that these p-subsequential labels (*subsequential_label*, ...,*subsequential_label - p - 1*) do not collide with existing labels. - DISAMBIGUATE: only the shortest path output for each input is retained, permissible when the semiring has the path property

- 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: r14 - 2015-07-15 - 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