Isomorphic
Description
This operations determines if two transducers have the same states, irrespecitve of numbering, and the same transitions with the same labels and weights, irrespective of ordering.
Usage
template <class Arc>
bool Isomorphic(const Fst<Arc> &fst1,
const Fst<Arc> &fst2,
double delta = kDelta);
|
[bad link?] |
fstisomorphic a.fst b.fst
|
Examples
Isomorphic(A, B); // returns true
Isomorphic(A, C); // returns false
$ if fstisomorphic a.fst b.fst; then echo true; else echo false; fi
true
$ if fstisomorphic a.fst c.fst; then echo true; else echo false; fi
false
Complexity
Isomorphic
- Time: O(V1 + V2 + E1 log D1 + E2 log D2)
- Space: O(D1 + D2)
where
Vi = # of states,
Ei = # of transitions,
Di = maximum
out-degree
Caveats
The inputs should be deterministic where each distinct
(input label, output label, weight)
triple of a transition is treated as a distinct label (e.g., deterministic after
Encode is performed on the labels and weights). If non-determinism in this sense is encountered, an error is raised.
These restrictions are imposed since the general solution is
graph isomorphism complete, a class believed to be between polynomial and NP-complete.
References
Zemlyachenko, Viktor N., Nickolay M. Korneenko, and Regina I. Tyshkevich. "Graph isomorphism problem." Journal of Soviet Mathematics 29.4 (1985): 1426-1481.