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

# 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 bool Isomorphic(const Fst &fst1, const Fst &fst2, double delta = kDelta); ``` [bad link?] ```fstisomorphic a.fst b.fst ```

## Examples

 `A` `B` `C`

```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
png iso1.png r1 manage 9.4 K 2014-04-23 - 00:26 MichaelRiley
png iso2.png r1 manage 9.5 K 2014-04-23 - 00:26 MichaelRiley
png iso3.png r1 manage 11.4 K 2014-04-23 - 00:26 MichaelRiley
Edit | Attach | Watch | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r2 - 2014-04-23 - MichaelRiley

Copyright © 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