TWiki> FST Web>FstQuickTour>EquivalentDoc (revision 5)EditAttach

# 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); ``` [bad link?] ```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
Edit | Attach | Watch | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r5 - 2014-04-23 - MichaelRiley

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