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 <class Arc>
bool Equivalent(const Fst<Arc> &fst1,
                const Fst<Arc> &fst2,
                double delta = kDelta);
doc
fstequivalent a.fst b.fst

Examples

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

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.

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.

-- CyrilAllauzen - 03 Mar 2009

Topic attachments
I Attachment History Action Size Date Who Comment
PNGpng equiv1.png r1 manage 15.1 K 2010-08-17 - 21:39 CyrilAllauzen Equivalent example: automaton A
PNGpng equiv2.png r1 manage 10.9 K 2010-08-17 - 21:39 CyrilAllauzen Equivalent example: automaton B
PNGpng equiv3.png r1 manage 11.4 K 2010-08-17 - 21:42 CyrilAllauzen Equivalent example: automaton C
Topic revision: r6 - 2014-04-23 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback