by rule applications, as will be formally defined later. As with simpler worlds described by facts only, deduction is not possible on inconsistent knowledge bases.

  **Person**  **in**  **Offic**
# Figure 8: A rule $\frac{}{}$. 
Evolution rules represent possible actions leading from one world to another one. E.g.

consider the colored graph of Figure 8. As an inference rule, it would allow to deduce that all persons are in all offices. As an evolution rule, it says that "when there are a person and an office, a possible action is to assign this office to that person". Consider a KB composed of a set of facts G , a set of evolution rules E , and a set of constraints C . Facts describe an initial world; evolution rules represent possible transitions from one world to other worlds; constraints define consistency of each world; a successor of a consistent world is obtained by an evolution rule application; given a SG Q, the deduction problem asks whether there is a path of consistent worlds evolving from the initial one to a world satisfying Q.

The most general model of the SG family considers both kinds of rules, i.e. a set R
of inference rules, and a set E of evolution rules. In the particular case of the SYSIPHUS-I
modelization, G and R describe the initial information about office locations, persons and the group organization. R also encodes general knowledge (such as properties of the dif relation put between two concept nodes representing distinct entities). C represents obligations and interdictions defining what acceptable assignments are (including cardinality constraints such as "a person cannot be in several offices" or "a large office cannot contain more than two persons", using the dif relation). E consists of one evolution rule whose result is to place a person into an office (it could also be composed of several rules considering specific preconditions before trying an assignment).  The goal represents a situation where each person of the group has an office. A solution to the problem is a world obtained from the initial one by a sequence of office assignments, where each person has an office, while satisfying the allocation constraints.

## 3.3 The Sg Family

Let us now specify definitions and notations concerning the SG family. Definition 5 (colored SGs) A colored simple graph is a pair K = (G,p) where G is a SG and ρ is a mapping from V(G) into {0,1}. The number associated to a node is called the color of the node. We denote by K (i) the subgraph of G induced by i-colored nodes. The subgraph K (0) must form a SG (i.e. the neighbors of a relation node of K (0) must also belong to K (0) )
The latter condition ( K (0) must form a SG) is necessary as soon as we consider rules as colored SGs: should a rule not satisfy this condition, its application on a SG could generate a graph that is not a SG.

A KB is denoted by K = ( G, R, E, C ), where G is a set of simple graphs representing facts, R, E and C are three sets of colored simple graphs respectively representing inference rules, evolution rules, and constraints (positive ones in C+, negative ones in C-). Given a