Thumbnail
Access Restriction
Open

Author Guinaldo, Olivier
Source CiteSeerX
Content type Text
Publisher Springer-Verlag
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Conceptual Graph ♦ Isomorphism Problem ♦ Structural Function ♦ Specialization Relation ♦ Projection Test ♦ Conceptual Graph Isomorphism Test ♦ Effective Search ♦ Structural Code ♦ Intrinsic Total Preorder ♦ Hashing Function ♦ Textual Code ♦ Large Conceptual Graph Set ♦ Total Order ♦ Filtering Code ♦ Structural Preordering Function ♦ Conceptual Graph Isomorphism ♦ Specialization Generalization Graph ♦ Conceptual Vertex
Description . The isomorphism problem is neither known to be NP-complete nor polynomial. Yet it is crucial for managing large conceptual graph sets. In order to speed up the conceptual graph isomorphism test, we associate to graphs a textual code that is invariant under isomorphism: a structural or filtering code. The structural code of a given graph is based on the computation by a structural function of an intrinsic total preorder on its conceptual vertices. Moreover for graphs for which the structural function produces a total order on conceptual vertices, two graphs which have the same code are isomorphic. Then, we present a conceptual graph set managing system based on the specialization relation and on a hashing function on the code induced by a structural C- preordering function. This system allows an effective search for a given conceptual graph according to its structure and so determines its specialization / generalization graphs without any projection test. 1 Introduction ...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1996-01-01
Publisher Institution In Proceedings of the 4th International Conference on Conceptual Structures, ICCS'96