ABSTRACT
This chapter overviews an idea to treat the Simple Conceptual Graphs (SCGs) with binary conceptual relations as a regular language, defined over the support symbols. These considerations are motivated by the need to provide fast conceptual search in run-time, a challenge that is viewed as one of the knowledge-processing bottlenecks in the emerging semantic systems. Our approach suggests an internal representation of the SCGs with binary conceptual relations, which is based on Finite State Automata (FSA), and provides extraordinary run-time speed in calculations of injective projections. The choice of FSA as supporting formalism is natural since the minimal deterministic FSA are known for their operational efficiency in many kinds of applications, including compact encodings of morphological dictionaries and ultra-fast text search. Actually the suggested idea is (i) to encode off-line the knowledge base of SCGs and all injective generalizations of all the subgraphs as a single, minimal acyclic FSA, thus preparing a compact conceptual archive of all possible SCGs having injective projections onto the given knowledge base, and (ii) to intersect in run-time the projection query with the minimal FSA, finding the projection answers in linear time that depends on the query length only. This two-stage approach to the calculation of injective
projection enables performing off-line the most time-consuming computations of subgraphs and their injective generalizations according to the knowledge base support. The critical point in such a scenario is to find suitable data structures, which store all resulting injective generalizations as a compact conceptual resource; fortunately the minimal acyclic FSA encode efficiently finite languages of words. To achieve our goals, we have to answer the following questions given a knowledge base of SCG with binary conceptual relations and its support:
• How to enumerate all injective generalizations of all the subgraphs in the knowledge base, keeping links to the original subgraphs for which the generalizations are computed?
