Difference: IsomorphicDoc (2 vs. 3)

Revision 32014-04-23 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Isomorphic Work in progress, under construction

Description

Changed:
<
<
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.
>
>
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

Line: 39 to 39
  Isomorphic
  • Time: O(V1 + V2 + E1 log D1 + E2 log D2)
Changed:
<
<
  • Space: O(D1 + D2)
>
>
  • Space: O(V1 + V2 + D1 + D2)
 where Vi = # of states, Ei = # of transitions, Di = maximum out-degree
Added:
>
>
#Caveats
 

Caveats

Changed:
<
<
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.
>
>
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.
 

References

 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback