Global Constraint Catalog: Kextensible

3.7.101. Extensible

$𝚊𝚕𝚕_𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ (extensible wrt $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ ),
$𝚊𝚗𝚍$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚅𝙰𝚁 = 0$ ),
$𝚊𝚜𝚜𝚒𝚐𝚗_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝𝚜$ (extensible wrt $𝙸𝚃𝙴𝙼𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [\geq, >]$ ),
$𝚊𝚜𝚜𝚒𝚐𝚗_𝚊𝚗𝚍_𝚗𝚟𝚊𝚕𝚞𝚎𝚜$ (extensible wrt $𝙸𝚃𝙴𝙼𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [\geq, >]$ ),
$𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ ),
$𝚊𝚝𝚕𝚎𝚊𝚜𝚝_𝚗𝚟𝚊𝚕𝚞𝚎$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ ),
$𝚊𝚝𝚕𝚎𝚊𝚜𝚝_𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ (extensible wrt $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ ),
$𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ ),
$𝚌𝚕𝚊𝚞𝚜𝚎_𝚊𝚗𝚍$ (extensible wrt $𝙿𝙾𝚂𝚅𝙰𝚁𝚂$ when $𝚅𝙰𝚁 = 0$ ),
$𝚌𝚕𝚊𝚞𝚜𝚎_𝚊𝚗𝚍$ (extensible wrt $𝙽𝙴𝙶𝚅𝙰𝚁𝚂$ when $𝚅𝙰𝚁 = 0$ ),
$𝚌𝚕𝚊𝚞𝚜𝚎_𝚘𝚛$ (extensible wrt $𝙿𝙾𝚂𝚅𝙰𝚁𝚂$ when $𝚅𝙰𝚁 = 1$ ),
$𝚌𝚕𝚊𝚞𝚜𝚎_𝚘𝚛$ (extensible wrt $𝙽𝙴𝙶𝚅𝙰𝚁𝚂$ when $𝚅𝙰𝚁 = 1$ ),
$𝚌𝚘𝚖𝚙𝚊𝚛𝚎_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ (extensible wrt $[𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2]$ when $𝙲𝙾𝚄𝙽𝚃 \in [\geq, >]$ ),
$𝚌𝚘𝚞𝚗𝚝$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [\geq, >]$ ),
$𝚌𝚘𝚞𝚗𝚝𝚜$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [\geq, >]$ ),
$𝚍𝚒𝚏𝚏𝚎𝚛_𝚏𝚛𝚘𝚖_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝_𝚔_𝚙𝚘𝚜$ (extensible wrt $[𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2]$ ),
$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ (suffix-extensible wrt $𝚃𝙰𝙱𝙻𝙴$ ),
$𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚙𝚛𝚘𝚍𝚞𝚌𝚝$ (suffix-extensible wrt $𝚃𝙰𝙱𝙻𝙴$ ),
$𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ (suffix-extensible wrt $𝚃𝙰𝙱𝙻𝙴$ ),
$𝚒𝚗$ (extensible wrt $𝚅𝙰𝙻𝚄𝙴𝚂$ ),
$𝚒𝚗_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕𝚜$ (extensible wrt $𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻𝚂$ ),
$𝚒𝚗_𝚛𝚎𝚕𝚊𝚝𝚒𝚘𝚗$ (extensible wrt $𝚃𝚄𝙿𝙻𝙴𝚂_𝙾𝙵_𝚅𝙰𝙻𝚂$ ),
$𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ (extensible wrt $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂$ ),
$𝚒𝚝𝚑_𝚙𝚘𝚜_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚏𝚛𝚘𝚖_0$ (suffix-extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ ),
$𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ (extensible wrt $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ ),
$𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ (suffix-extensible wrt $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ ),
$𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ (extensible wrt $[𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2]$ ),
$𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛$ (suffix-extensible wrt $[𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2]$ ),
$𝚕𝚎𝚡_𝚕𝚎𝚜𝚜$ (suffix-extensible wrt $[𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2]$ ),
$𝚗𝚊𝚗𝚍$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚅𝙰𝚁 = 1$ ),
$𝚗𝚌𝚕𝚊𝚜𝚜$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽𝙲𝙻𝙰𝚂𝚂 = | 𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂 |$ ),
$𝚗𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽𝙴𝚀𝚄𝙸𝚅 = 𝙼$ ),
$𝚗𝚘𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚅𝙰𝚁 = 0$ ),
$𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ ),
$𝚗𝚟𝚊𝚕𝚞𝚎𝚜$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [\geq, >]$ ),
$𝚗𝚟𝚊𝚕𝚞𝚎𝚜_𝚎𝚡𝚌𝚎𝚙𝚝_0$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [\geq, >]$ ),
$𝚗𝚟𝚎𝚌𝚝𝚘𝚛𝚜$ (extensible wrt $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [\geq, >]$ ),
$𝚘𝚙𝚎𝚗_𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ (suffix-extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ ),
$𝚘𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚅𝙰𝚁 = 1$ ),
$𝚛𝚊𝚗𝚐𝚎_𝚌𝚝𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [\geq, >]$ ),
$𝚜𝚌𝚊𝚕𝚊𝚛_𝚙𝚛𝚘𝚍𝚞𝚌𝚝$ (extensible wrt $𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼$ when $𝙲𝚃𝚁 \in [\geq, >]$ , $𝚖𝚒𝚗𝚟𝚊𝚕 (𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼 . 𝚌𝚘𝚎𝚏𝚏) \geq 0$ and $𝚖𝚒𝚗𝚟𝚊𝚕 (𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼 . 𝚟𝚊𝚛) \geq 0$ ),
$𝚜𝚘𝚖𝚎_𝚎𝚚𝚞𝚊𝚕$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ ),
$𝚜𝚝𝚊𝚐𝚎_𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ (suffix-extensible wrt $𝚃𝙰𝙱𝙻𝙴$ ),
$𝚜𝚞𝚖_𝚌𝚝𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [\geq, >]$ and $𝚖𝚒𝚗𝚟𝚊𝚕 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) \geq 0$ ),
$𝚜𝚞𝚖_𝚌𝚝𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [<, \leq]$ and $𝚖𝚊𝚡𝚟𝚊𝚕 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) \leq 0$ ),
$𝚜𝚞𝚖_𝚌𝚞𝚋𝚎𝚜_𝚌𝚝𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [\geq, >]$ and $𝚖𝚒𝚗𝚟𝚊𝚕 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) \geq 0$ ),
$𝚜𝚞𝚖_𝚌𝚞𝚋𝚎𝚜_𝚌𝚝𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [<, \leq]$ and $𝚖𝚊𝚡𝚟𝚊𝚕 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) \leq 0$ ),
$𝚜𝚞𝚖_𝚙𝚘𝚠𝚎𝚛𝚜 4_𝚌𝚝𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [\geq, >]$ ,
$𝚜𝚞𝚖_𝚙𝚘𝚠𝚎𝚛𝚜 5_𝚌𝚝𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [\geq, >]$ and $𝚖𝚒𝚗𝚟𝚊𝚕 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) \geq 0$ ),
$𝚜𝚞𝚖_𝚙𝚘𝚠𝚎𝚛𝚜 5_𝚌𝚝𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [<, \leq]$ and $𝚖𝚊𝚡𝚟𝚊𝚕 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) \leq 0$ ),
$𝚜𝚞𝚖_𝚙𝚘𝚠𝚎𝚛𝚜 6_𝚌𝚝𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [\geq, >]$ ,
$𝚜𝚞𝚖_𝚜𝚚𝚞𝚊𝚛𝚎𝚜_𝚌𝚝𝚛$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙲𝚃𝚁 \in [\geq, >]$ ,
$𝚞𝚜𝚎𝚍_𝚋𝚢$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ ),
$𝚞𝚜𝚎𝚍_𝚋𝚢_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ ),
$𝚞𝚜𝚎𝚍_𝚋𝚢_𝚖𝚘𝚍𝚞𝚕𝚘$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ ),
$𝚞𝚜𝚎𝚍_𝚋𝚢_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ ),
$𝚞𝚜𝚎𝚜$ (extensible wrt $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ ).

An extensible constraint is a constraint for which, given any satisfied ground instance (i.e., a source constraint), one can add any item without affecting that the resulting constraint (i.e., a target constraint) still holds, assuming all its restrictions holds. All the extensions of contractibility described at the corresponding keyword entry apply also for extensibility. In particular we also have the restricted notions of prefix-extensible and suffix-extensible constraints, which respectively means that items are added before the first item of a collection or after the last item. As for contractibility, extensibility may also be conditioned by a list of restrictions. Finally extensibility may involve more than one collection. In this context, items are added simultaneously to all collections from exactly the same set of positions. We now present different examples of extensible constraints, starting from a very simple one.

As a first example, consider the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ $(𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴)$ constraint, which forces at least $𝙽$ variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection to be assigned value $𝚅𝙰𝙻𝚄𝙴$ . We have that $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ is extensible with respect to $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , since adding a variable to an already satisfied instance of $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ preserves the fact that the new constraint is satisfied.

As an illustration consider the source constraint $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ $(2, 〈 4, 2, 4, 5 〉, 4)$ and the target constraint $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ $(2, 〈 4, 2, 4, 5, 0, 4 〉, 4)$ . Since the first argument $𝙽$ is set to the same value, both in the source and the target constraint, and since the third $𝚅𝙰𝙻𝚄𝙴$ is also set to the same value both in the source and the target constraint, we have that $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ $(2, 〈 4, 2, 4, 5 〉, 4)$ implies $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ $(2, 〈 4, 2, 4, 5, 0, 4 〉, 4)$ .
As a second example, consider the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(𝙸𝙽𝙳𝙴𝚇, 𝚃𝙰𝙱𝙻𝙴, 𝚅𝙰𝙻𝚄𝙴)$ constraint, which forces $𝚅𝙰𝙻𝚄𝙴$ to equal the ${𝙸𝙽𝙳𝙴𝚇}^{𝑡ℎ}$ item of $𝚃𝙰𝙱𝙻𝙴$ . We have that $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ is suffix-extensible with respect to $𝚃𝙰𝙱𝙻𝙴$ , since adding new elements at the end of $𝚃𝙰𝙱𝙻𝙴$ for an already satisfied instance of $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ preserves the fact that the new constraint is satisfied.

As an illustration consider the source constraint $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(3, 〈 6, 9, 2, 9 〉, 2)$ and the target constraint $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(3, 〈 6, 9, 2, 9, 8, 0, 2 〉, 2)$ . Since the first argument $𝙸𝙽𝙳𝙴𝚇$ is set to the same value, both in the source and the target constraint, and since the third argument $𝚅𝙰𝙻𝚄𝙴$ is also set to the same value both in the source and the target constraint, we have that $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(3, 〈 6, 9, 2, 9 〉, 2)$ implies $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(3, 〈 6, 9, 2, 9, 8, 0, 2 〉, 2)$ .
As a third example, consider the $𝚊𝚗𝚍$ $(𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint, which forces $𝚅𝙰𝚁$ to equal 1 if all variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are set to 1, and 0 otherwise. We have that $𝚊𝚗𝚍$ is extensible with respect to $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚅𝙰𝚁$ is equal to 0. This stems from the fact that, given a satisfied instance of $𝚊𝚗𝚍$ where $𝚅𝙰𝚁 = 0$ , adding any new variable to $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ preserves the fact that the new constraint is satisfied. As an illustration consider the source constraint $𝚊𝚗𝚍$ $(0, 〈 1, 0, 1 〉)$ and the target constraint $𝚊𝚗𝚍$ $(0, 〈 1, 0, 0, 1 〉)$ . Since the first argument $𝚅𝙰𝚁$ is set to 0, both in the source and the target constraint, we have that $𝚊𝚗𝚍$ $(0, 〈 1, 0, 1 〉)$ implies $𝚊𝚗𝚍$ $(0, 〈 1, 0, 0, 1 〉)$ .
As a fourth example, consider the $𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛$ $(𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2)$ constraint, which forces $𝚅𝙴𝙲𝚃𝙾𝚁 1$ to be lexicographically strictly greater than $𝚅𝙴𝙲𝚃𝙾𝚁 2$ . We have that $𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛$ is suffix-extensible with respect to $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ . This means that, given a satisfied instance of $𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛$ , adding $k$ items at the end of its first argument $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and adding $k$ other items at the end of its second argument $𝚅𝙴𝙲𝚃𝙾𝚁 2$ preserves the fact that the new constraint is satisfied.

As an illustration consider the source constraint $𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛$ $(〈 5, 2, 7, 1 〉,$ $〈 5, 2, 6, 2 〉)$ and the target constraint $𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛$ $(〈 5, 2, 7, 1, 0 〉,$ $〈 5, 2, 6, 2, 9 〉)$ . We have that $𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛$ $(〈 5, 2, 7, 1 〉,$ $〈 5, 2, 6, 2 〉)$ implies $𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛$ $(〈 5, 2, 7, 1, 0 〉,$ $〈 5, 2, 6, 2, 9 〉)$ .
As a fifth example, consider the $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ $(𝚅𝙴𝙲𝚃𝙾𝚁𝚂)$ constraint, which given a collection of vectors each of which defined by a collection of variables of the same length, forces the $i^{𝑡ℎ}$ vector to be lexicographically strictly less than the ${(i + 1)}^{𝑡ℎ}$ vector $(1 \leq i < | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |)$ . We have that $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ is suffix-extensible with respect to $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ . This means that, given a satisfied instance of $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ , adding $k$ items at the end of all collections simultaneously preserves the fact that the new constraint is satisfied.

As an illustration consider the source constraint $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ $(〈 𝚟𝚎𝚌 - 〈 5, 2, 3, 9 〉, 𝚟𝚎𝚌 - 〈 5, 2, 6, 2 〉, 𝚟𝚎𝚌 - 〈 5, 2, 6, 3 〉)$ and the target constraint $𝚕𝚎𝚡_𝚌𝚑𝚊𝚒𝚗_𝚕𝚎𝚜𝚜$ $(〈 𝚟𝚎𝚌 - 〈 5, 2, 3, 9, 9 〉, 𝚟𝚎𝚌 - 〈 5, 2, 6, 2, 8 〉, 𝚟𝚎𝚌 - 〈 5, 2, 6, 3, 7 〉)$ . Since each vector of the source constraint is a prefix of the vector located at the same position in the target constraint the source constraint implies the target constraint.

The keyword contractible introduces a dual notion, where items can be removed from a collection that is passed as an argument of a satisfied global constraint without affecting the fact that the resulting constraint is satisfied. Contractibility is a more common property than extensibility.

Global Constraint Catalog

3. Description of the Catalogue

3.7.101. Extensible