TWiki> FST Web>FstQuickTour>DeterminizeDoc (2019-02-24, MichaelRiley)

# Determinize

## Description

This operation determinizes a weighted transducer. The result will be an equivalent FST that has the property that no state has two transitions with the same input label. 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 void Determinize(const Fst &ifst, MutableFst *ofst); ``` ```template DeterminizeFst:: DeterminizeFst(const Fst &fst); ``` %DOX{fst::DeterminizeFst[ ]}% `fstdeterminize a.fst out.fst`

## Examples

### `A`: (TropicalWeight)

### `Determinize of A`: ```Determinize(&A);
DeterminizeFst<Arc>(A);
fstdeterminize a.fst out.fst
```

## Complexity

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

## Caveats

Epsilons may be added as input labels at the ends of paths when determinizing transducers. If input transducer also contains epsilons, this may result in a non-deterministic result even when the epsilons are treated as regular symbols. The subsequential label can be chosen as a non-zero value to avoid this issue by passing it as an option

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