Difference: DeterminizeDoc (1 vs. 16)

Revision 162019-02-24 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 75 to 75
  Efficient Algorithms for Testing the Twins Property. Journal of Automata, Languages and Combinatorics, 8(2):117-144, 2003.
Deleted:
<
<
-- MichaelRiley - 20 Jun 2007
 
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462224" name="determinize1.jpg" path="determinize1.jpg" size="12790" user="Main.MichaelRiley" version="2"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462225" name="determinize2.jpg" path="determinize2.jpg" size="14066" user="Main.MichaelRiley" version="2"

Revision 152018-04-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 17 to 17
 |
template <class Arc>
void Determinize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);
Changed:
<
<
| doc [bad link?] |
>
>
| |
 |
template <class Arc> DeterminizeFst<Arc>::
DeterminizeFst(const Fst<Arc> &fst);

Revision 142015-07-15 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 53 to 53
 The determinizable automata include all unweighted and all acyclic input.

Caveats

Changed:
<
<
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 (in a variant call to this function/class).
>
>
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

 
Deleted:
<
<
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.
 

See Also

Disambiguate, RmEpsilon

Revision 132014-05-06 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 52 to 52
  The determinizable automata include all unweighted and all acyclic input.
Added:
>
>

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 (in a variant call to this function/class).

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.

 

See Also

Disambiguate, RmEpsilon

Revision 122014-04-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 52 to 52
  The determinizable automata include all unweighted and all acyclic input.
Added:
>
>

See Also

Disambiguate, RmEpsilon

 

References

  • Mehryar Mohri.

Revision 112014-04-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Revision 102011-12-06 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 30 to 30
  determinize1.jpg
Added:
>
>
(TropicalWeight)
 

Determinize of A:

determinize2.jpg

Revision 92009-03-12 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 10 to 10
 

The transducer must be functional. The weights must be (weakly)

Changed:
<
<
left divisible (valid for TropicalWeight and LogWeight).
>
>
left divisible (valid for TropicalWeight and LogWeight for instance) and zero-sum-free.
 

Usage

|

Revision 82009-03-03 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 10 to 10
 

The transducer must be functional. The weights must be (weakly)

Changed:
<
<
left divisible (valid for TropicalWeight and LogWeight).
>
>
left divisible (valid for TropicalWeight and LogWeight).
 

Usage

|

Revision 72007-09-19 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 15 to 15
 

Usage

|
template <class Arc>
Changed:
<
<
void Determinize(MutableFst *fst);
>
>
void Determinize(const Fst &ifst, MutableFst *ofst);
 | doc [bad link?] | |
template <class Arc> DeterminizeFst<Arc>::

Revision 62007-07-02 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 41 to 41
 

Complexity

Determinize:
Changed:
<
<
  • determinizable: exponential (polynomial in the size of the output)
  • non-determinizable: does not terminate
>
>
  • Determinizable: exponential (polynomial in the size of the output)
  • Non-determinizable: does not terminate
 DeterminizeFst:
Changed:
<
<
  • Constructor: O(1)
  • Traversal:
    • determinizable: exponential (polynomial in the size of the output)
    • non-determinizable: does not terminate
>
>
  • Determinizable: exponential (polynomial in the size of the output)
  • Non-determinizable: does not terminate
  The determinizable automata include all unweighted and all acyclic input.

Revision 52007-06-30 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 6 to 6
 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.
Changed:
<
<
For this algorithm, epsilon transitions are treated as regular symbols (cf. RmEpsilon).
>
>
For this algorithm, epsilon transitions are treated as regular symbols (cf. RmEpsilon).
 

The transducer must be functional. The weights must be (weakly)

Revision 42007-06-26 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 13 to 13
 left divisible (valid for TropicalWeight and LogWeight).

Usage

Changed:
<
<
>
>
|
 template void Determinize(MutableFst *fst);
Changed:
<
<
>
>
| doc [bad link?] | |
 template DeterminizeFst:: DeterminizeFst(const Fst &fst);
Changed:
<
<
fstdeterminize a.fst out.fst
>
>
| doc |
fstdeterminize a.fst out.fst
 
 

Examples

Revision 32007-06-25 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 55 to 55
 
Changed:
<
<
Computational Linguistics, 23:2, 1997.
>
>
Computational Linguistics, 23:2, 1997.
  -- MichaelRiley - 20 Jun 2007

Revision 22007-06-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Determinize

Line: 51 to 51
  The determinizable automata include all unweighted and all acyclic input.
Added:
>
>

References

 -- MichaelRiley - 20 Jun 2007
Changed:
<
<
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182357485" name="determinize1.jpg" path="determinize1.jpg" size="12790" user="Main.MichaelRiley" version="2"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182357522" name="determinize2.jpg" path="determinize2.jpg" size="14066" user="Main.MichaelRiley" version="2"
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462224" name="determinize1.jpg" path="determinize1.jpg" size="12790" user="Main.MichaelRiley" version="2"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462225" name="determinize2.jpg" path="determinize2.jpg" size="14066" user="Main.MichaelRiley" version="2"

Revision 12007-06-20 - MichaelRiley

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="FstQuickTour"

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

Usage

template <class Arc>
void Determinize(MutableFst<Arc> *fst);

template <class Arc> DeterminizeFst<Arc>::
DeterminizeFst(const Fst<Arc> &fst);

fstdeterminize a.fst out.fst

Examples

A:

determinize1.jpg

Determinize of A:

determinize2.jpg

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:
  • Constructor: O(1)
  • Traversal:
    • determinizable: exponential (polynomial in the size of the output)
    • non-determinizable: does not terminate

The determinizable automata include all unweighted and all acyclic input.

-- MichaelRiley - 20 Jun 2007

META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182357485" name="determinize1.jpg" path="determinize1.jpg" size="12790" user="Main.MichaelRiley" version="2"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182357522" name="determinize2.jpg" path="determinize2.jpg" size="14066" user="Main.MichaelRiley" version="2"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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