TWiki> FST Web>FstQuickTour>EquivalentDoc (2018-04-27, MichaelRiley)

Equivalent

Description

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

 template bool Equivalent(const Fst &fst1, const Fst &fst2, double delta = kDelta); fstequivalent a.fst b.fst

Examples

 A B C   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

Equivalent

• Time:
• 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.

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.

-- CyrilAllauzen - 03 Mar 2009

Topic attachments
I Attachment History Action Size Date Who Comment png equiv1.png r1 manage 15.1 K 2010-08-17 - 21:39 CyrilAllauzen Equivalent example: automaton A png equiv2.png r1 manage 10.9 K 2010-08-17 - 21:39 CyrilAllauzen Equivalent example: automaton B png equiv3.png r1 manage 11.4 K 2010-08-17 - 21:42 CyrilAllauzen Equivalent example: automaton C
Topic revision: r7 - 2018-04-27 - MichaelRiley

Copyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback