TWiki> FST Web>FstQuickTour>IsomorphicDoc (revision 2)EditAttach

Isomorphic Work in progress, under construction

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);
doc [bad link?]
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(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.

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 | r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r2 - 2014-04-23 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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