Isomorphic

Description

This operations determines if two transducers have the same states and transitions irrespective of order.

Usage

template <class Arc> bool Isomorphic(const Fst<Arc> &fst1, const Fst<Arc> &fst2, double delta = kDelta);	[bad link?]
fstisomorphic a.fst b.fst

Complexity

Isomorphic

• Time: O(V₁ + V₂ + E₁ log D₁ + E₂ log D₂)
• Space: O(D₁ + D₂)

Caveats

The inputs should be deterministic where each distinct (input label, output label, weight) triple of a transition is treated as a distinct label. 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 thought 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.