Global Constraint Catalog: Carith

5.33. arith_sliding

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Used in the definition of some automaton

Constraint

$𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚁𝙴𝙻𝙾𝙿, 𝚅𝙰𝙻𝚄𝙴)$

Arguments

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚁𝙴𝙻𝙾𝙿$	$𝚊𝚝𝚘𝚖$
$𝚅𝙰𝙻𝚄𝙴$	$𝚒𝚗𝚝$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

𝚁𝙴𝙻𝙾𝙿 \in [=, \neq, <, \geq, >, \leq]

Purpose

Enforce for all sequences of variables ${𝚟𝚊𝚛}_{1}, {𝚟𝚊𝚛}_{2}, \dots, {𝚟𝚊𝚛}_{i}$ $(1 \leq i \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |)$ of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection to have $({𝚟𝚊𝚛}_{1} + {𝚟𝚊𝚛}_{2} + \dots + {𝚟𝚊𝚛}_{i}) 𝚁𝙴𝙻𝙾𝙿 𝚅𝙰𝙻𝚄𝙴$ .

Example

(〈0, 0, 1, 2, 0, 0, - 3〉, <, 4)

The $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint holds since all the following seven inequalities hold:

$0 < 4$ ,
$0 + 0 < 4$ ,
$0 + 0 + 1 < 4$ ,
$0 + 0 + 1 + 2 < 4$ ,
$0 + 0 + 1 + 2 + 0 < 4$ ,
$0 + 0 + 1 + 2 + 0 + 0 < 4$ ,
$0 + 0 + 1 + 2 + 0 + 0 - 3 < 4$ .

Typical

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 1

𝚁𝙴𝙻𝙾𝙿 \in [<, \geq, >, \leq]

Arg. properties

Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚁𝙴𝙻𝙾𝙿 \in [<, \leq]$ and $𝚖𝚒𝚗𝚟𝚊𝚕 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) \geq 0$ .
Suffix-contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

implies: $𝚜𝚞𝚖_𝚌𝚝𝚛$ .

part of system of constraints: $𝚊𝚛𝚒𝚝𝚑$ .

used in graph description: $𝚊𝚛𝚒𝚝𝚑$ .

Keywords

characteristic of a constraint: hypergraph, automaton, automaton with counters.

combinatorial object: sequence.

constraint type: arithmetic constraint, decomposition, sliding sequence constraint.

Arc input(s): $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$
Arc generator: $𝑃𝐴𝑇𝐻_1$ $\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗$
Arc arity: $*$
Arc constraint(s): $𝚊𝚛𝚒𝚝𝚑$ $(𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗, 𝚁𝙴𝙻𝙾𝙿, 𝚅𝙰𝙻𝚄𝙴)$
Graph property(ies): $𝐍𝐀𝐑𝐂$ $= | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$

Automaton: Figure 5.33.1 depicts the automaton associated with the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint. To each item of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a signature variable $S_{i}$ that is equal to 0.

Figure 5.33.1. Automaton of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint ( $T$ is initially set to 1 and reset to 0 as soon as one of the sliding constraints does not hold)

Figure 5.33.2. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )

Global Constraint Catalog

5. Global Constraint Catalogue

5.33. arith_sliding

Figure 5.33.1. Automaton of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint ( $T$ is initially set to 1 and reset to 0 as soon as one of the sliding constraints does not hold)

Figure 5.33.2. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )

Global Constraint Catalog

5. Global Constraint Catalogue

5.33. arith_sliding

Figure 5.33.1. Automaton of the 𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐 constraint (T is initially set to 1 and reset to 0 as soon as one of the sliding constraints does not hold)

Figure 5.33.2. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the 𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐 constraint (since all states of the automaton are accepting there is no restriction on the last variable Q n )

Figure 5.33.1. Automaton of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint ( $T$ is initially set to 1 and reset to 0 as soon as one of the sliding constraints does not hold)

Figure 5.33.2. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )