| 摘要 |
Two methods and systems for fast construction of poset isomorphism certificates are provided. Posets (partially-ordered sets) generalize graphs. The invented certificates are number sequences such that two posets are isomorphic if and only if their corresponding certificates coincide. The first method yields the (Omicron,Iota) poset isomorphism certificate. The minimal Phi-isomorphism certificate can be constructed by partitioning vertices of the graphs into Phi-ranked symmetry clusters and constructing a topological Phi-vertex ranking. Thus, symmetries in posets are detectable at low cost. In addition, the Phi-vertex ranking and a poset isomorphism certificate provide a pair of separate one-dimensional keys for poset encoding. Data objects representable as posets, which are commonly used in automated design, safety and security applications, biocomputing, management of semi-structured data, and other fields, can be stored, analyzed, indexed, and accessed using the isomorphism certificates requiring much less storage and computation time.
|
