Extensions of Simple Conceptual Graphs: the Complexity of Rules and
  Constraints
  Simple conceptual graphs are considered as the kernel of most knowledge
representation formalisms built upon Sowa's model. Reasoning in this model can
be expressed by a graph homomorphism called projection, whose semantics is
usually given in terms of positive, conjunctive, existential FOL. We present
here a family of extensions of this model, based on rules and constraints,
keeping graph homomorphism as the basic operation. We focus on the formal
definitions of the different models obtained, including their operational
semantics and relationships with FOL, and we analyze the decidability and
complexity of the associated problems (consistency and deduction). As soon as
rules are involved in reasonings, these problems are not decidable, but we
exhibit a condition under which they fall in the polynomial hierarchy. These
results extend and complete the ones already published by the authors. Moreover
we systematically study the complexity of some particular cases obtained by
restricting the form of constraints and/or rules.
