Global Constraint Catalog: Celementn

5.145. elementn

DESCRIPTION

LINKS

AUTOMATON

Origin

P. Flener

Constraint

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗 (𝙸𝙽𝙳𝙴𝚇, 𝚃𝙰𝙱𝙻𝙴, 𝙴𝙽𝚃𝚁𝙸𝙴𝚂)$

Arguments

$𝙸𝙽𝙳𝙴𝚇$	$𝚍𝚟𝚊𝚛$
$𝚃𝙰𝙱𝙻𝙴$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚕𝚞𝚎 - 𝚒𝚗𝚝)$
$𝙴𝙽𝚃𝚁𝙸𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚎𝚗𝚝𝚛𝚢 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝙸𝙽𝙳𝙴𝚇 \geq 1

𝙸𝙽𝙳𝙴𝚇 \leq | 𝚃𝙰𝙱𝙻𝙴 | - | 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 | + 1

| 𝚃𝙰𝙱𝙻𝙴 | > 0

| 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 | > 0

| 𝚃𝙰𝙱𝙻𝙴 | \geq | 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚃𝙰𝙱𝙻𝙴, 𝚟𝚊𝚕𝚞𝚎)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙴𝙽𝚃𝚁𝙸𝙴𝚂, 𝚎𝚗𝚝𝚛𝚢)

Purpose

$\forall i \in [1, | 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 |] : 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 [i] . 𝚎𝚗𝚝𝚛𝚢 = 𝚃𝙰𝙱𝙻𝙴 [𝙸𝙽𝙳𝙴𝚇 + i - 1] . 𝚟𝚊𝚕𝚞𝚎$

Example

(3, 〈6, 9, 2, 9〉, 〈2, 9〉)

The $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ constraint holds since its third argument $𝙴𝙽𝚃𝚁𝙸𝙴𝚂 = 〈 2, 9 〉$ is set to the subsequence starting at the third (i.e., $𝙸𝙽𝙳𝙴𝚇 = 3$ ) item of the table $𝚃𝙰𝙱𝙻𝙴 = 〈 6, 9, 2, 9 〉$ .

Typical

| 𝚃𝙰𝙱𝙻𝙴 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝙱𝙻𝙴 . 𝚟𝚊𝚕𝚞𝚎) > 1

| 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 | > 1

Symmetry

All occurrences of two distinct values in $𝚃𝙰𝙱𝙻𝙴 . 𝚟𝚊𝚕𝚞𝚎$ or $𝙴𝙽𝚃𝚁𝙸𝙴𝚂 . 𝚎𝚗𝚝𝚛𝚢$ can be swapped; all occurrences of a value in $𝚃𝙰𝙱𝙻𝙴 . 𝚟𝚊𝚕𝚞𝚎$ or $𝙴𝙽𝚃𝚁𝙸𝙴𝚂 . 𝚎𝚗𝚝𝚛𝚢$ can be renamed to any unused value.

Arg. properties

Suffix-extensible wrt. $𝚃𝙰𝙱𝙻𝙴$ .

Usage

The $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ constraint is useful for extracting of subsequence of fixed length from a given sequence.

Reformulation

Let $I_{1} = 𝙸𝙽𝙳𝙴𝚇, I_{2} = 𝙸𝙽𝙳𝙴𝚇 + 1, \dots, I_{| 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 |} = 𝙸𝙽𝙳𝙴𝚇 + | 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 | - 1$ . The $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ $(𝙸𝙽𝙳𝙴𝚇, 𝚃𝙰𝙱𝙻𝙴, 〈 𝚎𝚗𝚝𝚛𝚢 - E_{1}, 𝚎𝚗𝚝𝚛𝚢 - E_{2}, \dots, 𝚎𝚗𝚝𝚛𝚢 - E_{| 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 |} 〉)$ constraint can be expressed in term of a conjunction of $| 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 |$ $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraints of the form:

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(I_{1}, 𝚃𝙰𝙱𝙻𝙴, E_{1})$ ,

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(I_{2}, 𝚃𝙰𝙱𝙻𝙴, E_{2})$ ,

$\dots$

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(𝙸𝙽𝙳𝙴𝚇 + | 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 | - 1, 𝚃𝙰𝙱𝙻𝙴, E_{| 𝙴𝙽𝚃𝚁𝙸𝙴𝚂 |})$ .

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

constraint network structure: Berge-acyclic constraint network.

constraint type: data constraint, sliding sequence constraint.

filtering: arc-consistency.

modelling: table.

Automaton: Figure 5.145.1 depicts the automaton associated with the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ constraint of the Example slot. Let $𝙸$ and $𝙴_{k}$ respectively denote the $𝙸𝙽𝙳𝙴𝚇$ argument and the $𝚎𝚗𝚝𝚛𝚢$ attribute of the $k^{t h}$ item of the $𝙴𝙽𝚃𝚁𝙸𝙴𝚂$ collection. Figure 5.145.2 depicts the reformulation of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ constraint.

Figure 5.145.1. Automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ constraint given in the example

Figure 5.145.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.145. elementn

Figure 5.145.1. Automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ constraint given in the example

Figure 5.145.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.145. elementn

Figure 5.145.1. Automaton of the 𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗 constraint given in the example

Figure 5.145.2. Hypergraph of the reformulation corresponding to the automaton of the 𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗 constraint

Figure 5.145.1. Automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ constraint given in the example

Figure 5.145.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚗$ constraint