Title: On generalization/specialization for conceptual graphs
Abstract:Abstract Abstract This paper centres on the generalization/specialization relation in the framework of conceptual graphs (this relation corresponds to logical subsumption when considering logical form...Abstract Abstract This paper centres on the generalization/specialization relation in the framework of conceptual graphs (this relation corresponds to logical subsumption when considering logical formulas associated with conceptual graphs). Results given here apply more generally to any model where knowledge is described by labelled graphs and reasoning is based on graph subsumption, as in semantic networks or in structural machine learning. The generalization/specialization relation, as defined by Sowa, is first precisely analysed, in particular its links with a graph morphism, called projection. Besides Sowa's specialization relation (which is a preorder), another one is actually used in some practical applications (which is an order). These are comparatively studied. The second topic of this paper is the design of efficient algorithms for computing these specialization relations. Since the associated problems are NP-hard, the form of the graphs is restricted in order to arrive at polynomial algorithms. In particular, polynomial algorithms are presented for computing a projection from a conceptual 'tree' to any conceptual graph, and for counting the number of such projections. The algorithms are also described in a generic way, replacing the projection by a parametrized graph morphism, and conceptual graphs by directed labelled graphs. Keywords: subsumptionconceptual graphslabelled graphsgraph morphismspolynomial algorithms.Read More
Publication Year: 1995
Publication Date: 1995-07-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 54
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot