Nested Graphs: A Graph-based Knowledge Representation Model with FOL Semantics.
Michel Chein, Marie-Laure Mugnier, Geneviève Simonet · 1998
We present a graph-based KR model issued from Sowa's conceptual graphs but studied and developed with a speci c approach. Formal objects are kinds of labelled graphs, which maybesimple graphs or nested graphs. The fundamental notion for doing reasonings, called projection (or subsumption), is a kind of labelled graph morphism. Thus, we propose a graphical KR model, where \\graphical " is used in the sense of [Sch91], i.e. a model that \\uses graph-theoretic notions in an essential and nontrivial way". Indeed, morphism, which is the fundamental notion for any structure, is at the core of our theory. We de ne two rst order logic semantics, which correspond to di erentintuitivesemantics, and proveinboth cases that projection is sound and complete with respect to deduction. This paper is almost identical to the paper ap-peared in the KR'98 proceedings. It provides mi-nor corrections. 1