Global Constraint Catalog: Carith

5.26. 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}, ..., {𝚟𝚊𝚛}_{i}$ $(1 \leq i \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |)$ of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection to have $({𝚟𝚊𝚛}_{1} + {𝚟𝚊𝚛}_{2} + ... + {𝚟𝚊𝚛}_{i}) 𝚁𝙴𝙻𝙾𝙿 𝚅𝙰𝙻𝚄𝙴$ .

Example

(\begin{matrix} 〈\begin{matrix} 𝚟𝚊𝚛 - 0, \\ 𝚟𝚊𝚛 - 0, \\ 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 2, \\ 𝚟𝚊𝚛 - 0, \\ 𝚟𝚊𝚛 - 0, \\ 𝚟𝚊𝚛 - - 3 \end{matrix}〉, <, 4 \end{matrix})

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

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.26.1 depicts the automaton associated with the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint. To each item of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a signature variable $𝚂_{i}$ that is equal to 0.

Figure 5.26.1. Automaton of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint

Figure 5.26.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.26. arith_sliding

Figure 5.26.1. Automaton of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint

Figure 5.26.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint

W3C: XHTML - last update: 2010-12-6. SD.

Global Constraint Catalog

5. Global Constraint Catalogue

5.26. arith_sliding

Figure 5.26.1. Automaton of the 𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐 constraint

Figure 5.26.2. Hypergraph of the reformulation corresponding to the automaton of the 𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐 constraint

W3C: XHTML - last update: 2010-12-6. SD.

Figure 5.26.1. Automaton of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint

Figure 5.26.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚊𝚛𝚒𝚝𝚑_𝚜𝚕𝚒𝚍𝚒𝚗𝚐$ constraint