# Constraint extension

Extensional constraints, also called table constraints (especially, when constraint arity is large), are defined by enumerating the list of tuples that are allowed (supports) or forbidden (conflicts).

A constraint *extension* contains then two elements. The first element is an element list that indicates the scope of the constraint (necessarily a list of variable ids). The second element is either an element supports or an element conflicts, depending on the semantics of the (ordinary) tuples that are listed in lexicographic order within the element.

## Positive Table Constraints

Positive table constraints are defined from supports.

The syntax for *unary* extensional positive constraints is:

#### Syntax

```
<extension>
<list> intVar </list>
<supports> ((intVal | intIntvl) wspace)\* </supports>
</extension>
```

The syntax for *non-unary* extensional positive constraints is:

#### Syntax

```
<extension>
<list> (intVar wspace)2+ </list>
<supports> ("(" intVal ("," intVal)+ ")")\* </supports>
</extension>
```

An example is given below with a unary constraint involving x, with {1,2,4,8,9,10} as supports, and a ternary constraint involving y1, y2 and y3, with {(0, 1, 0),(1,0,0),(1,1,0),(1,1,1)} as supports.

#### Example

```
<extension id="c1">
<list> x </list>
<supports> 1 2 4 8..10 </supports>
</extension>
<extension id="c2">
<list> y1 y2 y3 </list>
<supports> (0,1,0)(1,0,0)(1,1,0)(1,1,1) </supports>
</extension>
```

## Negative Table Constraints

Negative table constraints are defined from conflicts.

The syntax for *unary* extensional negative constraints is:

#### Syntax

```
<extension>
<list> intVar </list>
<conflicts> ((intVal | intIntvl) wspace)\* </conflicts>
</extension>
```

The syntax for *non-unary* extensional negative constraints is:

#### Syntax

```
<extension>
<list> (intVar wspace)2+ </list>
<conflicts> ("(" intVal ("," intVal)+ ")")\* </conflicts>
</extension>
```

An example is given below with a unary constraint involving x, with {2,6} as conflicts, and a quaternary constraint involving y1, y2, y3 and y4, with {(1, 2, 3, 4),(3,1,3,4)} as conflicts.

#### Example

```
<extension>
<list> x </list>
<conflicts> 2 6 </conflicts>
</extension>
<extension>
<list> y1 y2 y3 y4 </list>
<conflicts> (1,2,3,4)(3,1,3,4) </conflicts>
</extension>
```

## Non-ordinary Tables

We now introduce extended forms of non-unary table constraints: they involve * non-ordinary * tuples, i.e., *short* or *compressed* tuples. On the one hand, it may be particularly useful to integrate short tuples (based on so-called short supports) in tables. This means that we can insert the special symbol “*” in tuples to represent any possible value, for the associated variable(s).

For example, the following constraint has two short tuples, (1,*,1,2) and (2,1,*,*). Assuming that the domain of all variables is {1,2}, the first short tuple is equivalent to the two (long) tuples (1,1,1,2) and (1,2,1,2) whereas the second short tuple is equivalent to the four tuples (2,1,1,1), (2,1,1,2), (2,1,2,1) and (2,1,2,2).

#### Example

```
<extension>
<list> z1 z2 z3 z4 </list>
<supports> (1,*,1,2)(2,1,*,*) </supports>
</extension>
```

On the other hand, to reduce space complexity, one may also seek to integrate compressed tuples in tables. This means that tuples can contain not only usual integer values, but also sets of integer values. The set of classical tuples represented by a compressed tuple τ is then the Cartesian product built from the components of τ. For example, in the following constraint, (0,{1,2},0,{0,2}) is a compressed tuple representing the set of ordinary tuples in {0}×{1,2}×{0}×{0,2}, which contains (0,1,0,0), (0,1,0,2), (0,2,0,0) and (0,2,0,2).

#### Example

```
<extension>
<list> w1 w2 w3 w4 </list>
<supports> (0,{1,2},0,{0,2})(1,0,1,2)(2,{0,2},0,2) </supports>
</extension>
```

In XCSP^{3}-core, short tuples are considered, contrary to compressed tuples.