Knowledge Representation and Reasonings Based on Graph
Homomorphism
Marie-Laure Mugnier
email: mugnier@lirmm.fr
In Conceptual Structures: Logical, Linguistic, and Computational Issues
Proceedings of the 8th International Conference on Conceptual Structures (ICCS 2000)
© Springer
Abstract:
The main conceptual contribution in this paper is to present an
approach to knowledge representation and reasonings based on labeled
graphs and labeled graph homomorphism. Strengths and weaknesses of
this graph-based approach are discussed. Main technical contributions
are the followings. Fundamental results about the
kernel of this approach, the so-called simple graphs model are
synthesized. It is then shown that the basic deduction problem on simple graphs
is essentially the same problem as conjunctive query containment in
databases and constraint satisfaction; polynomial
parsimonious transformations between these problems are exhibited.
Grounded on the simple graphs model, a knowledge representation
and reasoning model allowing to deal with facts, production rules,
transformation rules, and constraints is presented, as an
illustration of the graph-based approach.
