Difference: EquivalentDoc (1 vs. 7)

Revision 72018-04-27 - MichaelRiley

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

Equivalent

Line: 13 to 13
 bool Equivalent(const Fst &fst1, const Fst &fst2, double delta = kDelta);
Changed:
<
<
| %DOX{namespacefst.html#Equivalent[doc]}% |
>
>
|
 |
fstequivalent a.fst b.fst
Changed:
<
<
||
>
>
|
 

Examples

Revision 62014-04-23 - MichaelRiley

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

Equivalent

Line: 47 to 47
  Weighted equivalence is sensitive to machine precision when using floating-point-based weights especially with non-integral values. Consider using RandEquivalent instead.
Added:
>
>

See Also

Equal, Isomorphic, RandEquivalent

 

References

  • Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. "The Design and Analysis of Computer Programs". Addison-Wesley, 1974.

Revision 52014-04-23 - MichaelRiley

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

Equivalent

Description

Changed:
<
<
This operations determines if two epsilon-free deterministic weighted acceptors are equivalent, that is if they accept the same strings with the same weights.
>
>
This operation determines if two epsilon-free deterministic weighted acceptors are equivalent, that is if they accept the same strings with the same weights.
 

Usage

Revision 42014-04-23 - MichaelRiley

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

Equivalent

Line: 18 to 18
 fstequivalent a.fst b.fst ||
Changed:
<
<

Example

>
>

Examples

 
A B C
equiv1.png equiv2.png equiv3.png

Revision 32014-03-24 - MichaelRiley

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

Equivalent

Line: 43 to 43
 where n = V1 + V2 with Vi = # of states, d is the maximal out-degree and G(n) is a very slowly growing function that can be approximated by 4 by all practical purposes.
Added:
>
>

Caveats

Weighted equivalence is sensitive to machine precision when using floating-point-based weights especially with non-integral values. Consider using RandEquivalent instead.

 

References

  • Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. "The Design and Analysis of Computer Programs". Addison-Wesley, 1974.

Revision 22010-08-17 - CyrilAllauzen

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

Equivalent

Description

Changed:
<
<
Work in progress, under construction This operations determines if two epsilon-free deterministic weighted acceptors are equivalent.
>
>
This operations determines if two epsilon-free deterministic weighted acceptors are equivalent, that is if they accept the same strings with the same weights.
 

Usage

Line: 20 to 20
 

Example

Changed:
<
<
Work in progress, under construction TBA
>
>
A B C
equiv1.png equiv2.png equiv3.png

Equivalent(A, B);  // returns true
Equivalent(A, C); // returns false

$ if fstequivalent a.fst b.fst; then echo true; else echo false; fi
true
$ if fstequivalent a.fst c.fst; then echo true; else echo false; fi
false
 

Complexity

Deleted:
<
<
Work in progress, under construction
 Equivalent
  • Time:
Changed:
<
<
    • Unweighted: quasi-linear, i.e. O(n G(n))
    • Weighted: complexity of unweighted + complexity of shortest-distance
  • Space: quasi-linear, i.e. O(n G(n))
where n = V1 + V2 with Vi = # of states and G(n) is a very slowly growing function that can be approximated by 4 by all practical purposes.
>
>
    • Unweighted: quasi-linear, i.e. O(d n G(n))
    • Weighted: complexity of unweighted + complexity of weight-pushing
  • Space: linear, i.e. O(n + d)
where n = V1 + V2 with Vi = # of states, d is the maximal out-degree and G(n) is a very slowly growing function that can be approximated by 4 by all practical purposes.
 

References

Line: 38 to 48
 
  • Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. "The Design and Analysis of Computer Programs". Addison-Wesley, 1974.

-- CyrilAllauzen - 03 Mar 2009

Added:
>
>
META FILEATTACHMENT attachment="equiv1.png" attr="" comment="Equivalent example: automaton A" date="1282081141" name="equiv1.png" path="equiv1.png" size="15468" stream="equiv1.png" tmpFilename="/var/tmp/CGItemp26577" user="CyrilAllauzen" version="1"
META FILEATTACHMENT attachment="equiv2.png" attr="" comment="Equivalent example: automaton B" date="1282081174" name="equiv2.png" path="equiv2.png" size="11111" stream="equiv2.png" tmpFilename="/var/tmp/CGItemp26834" user="CyrilAllauzen" version="1"
META FILEATTACHMENT attachment="equiv3.png" attr="" comment="Equivalent example: automaton C" date="1282081346" name="equiv3.png" path="equiv3.png" size="11702" stream="equiv3.png" tmpFilename="/var/tmp/CGItemp26642" user="CyrilAllauzen" version="1"

Revision 12009-03-03 - CyrilAllauzen

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

Equivalent

Description

Work in progress, under construction This operations determines if two epsilon-free deterministic weighted acceptors are equivalent.

Usage

template <class Arc>
bool Equivalent(const Fst<Arc> &fst1,
                const Fst<Arc> &fst2,
                double delta = kDelta);
%DOX{namespacefst.html#Equivalent[doc]}%
fstequivalent a.fst b.fst

Example

Work in progress, under construction TBA

Complexity

Work in progress, under construction Equivalent

  • Time:
    • Unweighted: quasi-linear, i.e. O(n G(n))
    • Weighted: complexity of unweighted + complexity of shortest-distance
  • Space: quasi-linear, i.e. O(n G(n))
where n = V1 + V2 with Vi = # of states and G(n) is a very slowly growing function that can be approximated by 4 by all practical purposes.

References

  • Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. "The Design and Analysis of Computer Programs". Addison-Wesley, 1974.

-- CyrilAllauzen - 03 Mar 2009

 
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