Equivalent
Description
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
template <class Arc>
bool Equivalent(const Fst<Arc> &fst1,
const Fst<Arc> &fst2,
double delta = kDelta);
|
[bad link?] |
fstequivalent a.fst b.fst
|
Example
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.
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