EquivalentDoc < FST

---+ Equivalent

---++ Description

This operation determines if two epsilon-free deterministic weighted acceptors are [[FstGlossary#EquivalentDef][equivalent]], that is if they accept the same strings with the same weights.

---++ Usage

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

---++ Examples

| ==A== | ==B== | ==C==|
| %ATTACHURL%/equiv1.png |  %ATTACHURL%/equiv2.png |  %ATTACHURL%/equiv3.png | 

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

---++ Complexity

=Equivalent=
   * Time:
      * _Unweighted_: quasi-linear, i.e. _O(d n G(n))_
      * _Weighted_:  complexity of unweighted + complexity of [[PushDoc#Complexity][weight-pushing]]
   * Space:  linear, i.e. _O(n + d)_
where _n_ = _V<sub>1</sub>_ + _V<sub>2</sub>_ with _V<sub>i</sub>_ = # 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 [[RandEquivalentDoc][RandEquivalent]] instead.

---++ References

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

-- Main.CyrilAllauzen - 03 Mar 2009

Attachments

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

This topic: FST > WebHome > FstQuickTour > EquivalentDoc
Topic revision: r5 - 2014-04-23 - MichaelRiley