[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publications: [PUBLink] [PUBLink] [PUBLink])

A conventional CSP's constraint correlates domain values. In contrast, a structural constraint correlates subgraphs. A conventional constraint's application point is defined by the problem formulation, whereas a structural constraint's application point is not clear in advance. Thus, a structural constraint needs a matching part that is equal to the left-hand side of a production rule (docking part S_d).

A conventional constraint is true as long as there is at least one tuple of possible variable assignments. There may be a few possible structures to be accepted by a structural constraint as well. Thus, structural constraints do not have only one right-hand side, like a production, but a set of alternatives (testing part S_t). These alternatives have a testing nature and are not used for pushouts like the production's right-hand side. Because of this, there may be application conditions not only for the docking part, but also for the testing part's alternatives.

If the docking part S_d of a structural constraint S = (S_d, S_t) matches the constraint graph, an alternative of the testing part S_t has to match too. A graph g is structurally consistent iff there exists a morphism T: a g,   a S_t for every structural constraint S and every possible match D: S_d g such that T · (S_d a) = D.

The example structural constraint S_C1 that is shown below states the condition that if the constraint graph contains the tasks Cast Spell and Drink Potion then the tasks must be related to different persons (testing part 1) or they must be related to a temporal Non-Overlap constraint (testing part 2).

Heckel and Wagner [PUBLink] introduce so-called consistency conditions that are equal to structural constraints, with a testing part consisting of one alternative only. These can be directly transformed into semantically equivalent application conditions of productions.

For questions, comments or suggestions, please contact us.

Last update:
January 31, 2002 by Alexander Nareyek