of richer knowledge bases composed of rules (as in SRC ) and they are not integrated into more complex reasonings (as in SEC or in SREC ).

There should be other connections with works about verification of knowledge bases composed of logical rules (for instance Horn rules), namely with the works of Levy and Rousset (1996), in which constraints are TGDs, thus have the same form than ours, but we did not find direct relationships between their framework and ours.

As both models are rooted in semantic networks, comparing conceptual graphs and descriptions logics is a problem that has often been issued. Baader, Molitor, and Tobies
(1999) have identified a fragment of the SG model (where simple graphs are restricted to those having a tree-like structure, but conjunctive types are allowed) with a language called ELIRO 1 : this equivalence has led to a new tractability result in description logics. However, trying to identify larger fragments seems to be a dead-end: as pointed out by Mugnier (2000),
projection cannot handle negation on primitive types. On the other hand, even the most expressive description logics cannot express the whole FOL( Λ, ∃ ) fragment (Borgida, 1996).

Encoding some existing description logics into models of the SG family is an interesting perspective, that could allow one to identify new decidable classes for our models, add type expressiveness to conceptual graphs, and may be cycles in the description of DLs concepts.

## 9. Conclusion

We have proposed a family of models that can be seen as the basis of a generic modeling framework. Main features of this framework are the following: a clear distinction between different kinds of knowledge, that fit well with intuitive categories, a uniform graph-based language that keeps essential properties of the SG model, namely readability of objects as well as reasonings. We guess this latter point is particularly important for the usability of any knowledge based system. In our framework, all kinds of knowledge are graphs easily interpreted, and reasonings can be graphically represented in a natural manner using the graphs themselves, thus explained to the user on its own modelization.

Technical contributions, w.r.t. previous works on conceptual graphs, can be summarized as follows:

- the representation of different kinds of knowledge as colored SGs: facts, inference rules, evolution rules and constraints.

- the integration of constraints into a reasoning model; more or less similar notions of a constraint had already been introduced but were only used to check consistency of a simple graph (as in the SGC model). The complexity of consistency checking was not known.

- a systematic study of the obtained family of models with a complexity classification of associated consistency/deduction problems, including the study of particular cases of rules and constraints, which provide interesting complexity results.
We also established links between consistency checking and FOL deduction, translating the consistency /deduction problems in terms of FOL deduction.  It should be noticed that the operational semantics of models combining rules and constraints, namely SREC, SRC and SEC , is easy to understand but we were not able to give a global logical semantics. Indeed,