Isomorphic

Description

This operation determines if two transducers with a certain required determinism have the same states, irrespective of numbering, and the same transitions with the same labels and weights, irrespective of ordering. In other words, Isomorphic(A, B) is true if and only if the states of A can be renumbered and the transitions leaving each state reordered so that Equal(A, B) is true.

Usage

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

Examples

A B C
iso1.png iso2.png iso3.png

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(V1 + V2 + D1 + D2)
where Vi = # of states, Ei = # of transitions, Di = maximum out-degree

Caveats

The inputs should be deterministic in the sense that no state has two transitions with the same input label, output label and weight (e.g., deterministic after Encode is performed on the labels and weights). If non-determinism in this sense is encountered, an error is raised. This requirement is imposed since the general solution is graph isomorphism complete, for which no known polynomial-time algorithm exists.

See Also

Equal, Equivalent, RandEquivalent

References

Zemlyachenko, Viktor N., Nickolay M. Korneenko, and Regina I. Tyshkevich. "Graph isomorphism problem." Journal of Soviet Mathematics 29.4 (1985): 1426-1481.

Topic attachments
I Attachment History Action Size Date Who Comment
PNGpng iso1.png r1 manage 9.4 K 2014-04-23 - 00:26 MichaelRiley  
PNGpng iso2.png r1 manage 9.5 K 2014-04-23 - 00:26 MichaelRiley  
PNGpng iso3.png r1 manage 11.4 K 2014-04-23 - 00:26 MichaelRiley  
Edit | Attach | Watch | Print version | History: r6 < r5 < r4 < r3 < r2 | Backlinks | Raw View | WYSIWYG | More topic actions
Topic revision: r6 - 2018-04-27 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback