#### Characteristic Set Constraints

In order to formulate the constraints that will only license tree-shaped solved forms, we must first consider each individual case for . For each case and its negation , we will formulate characteristic constraints involving the set variables that we introduced above.

Let's consider the case for which a solution looks as shown below:

For convenience, we define, for each variable , the additional set variables and as follows:

We write for the constraint characteristic of case and define it as follows:

I.e. all variables equal or below are below , all variables equal or above are above , and all variables disjoint from are also disjoint from . This illustrates how set constraints permit to succinctly express certain patterns of inference. Namely precisely expresses:

The negation is somewhat simpler and states that no variable equal to is above , and no variable equal to is below . Remember that expresses that and are disjoint.

We can define the other cases similarly. Thus :

and its negation :

For the case we first introduce notation. We write for the tuple defined as follows:

where when the constraint occurs in (more about this when presenting the problem-specific constraints). Now we can simply define as:

and its negation as:

Denys Duchier
Version 1.2.0 (20010221)