Global Constraint Catalog: Cinflexion

5.164. inflexion

DESCRIPTION

LINKS

AUTOMATON

Origin

N. Beldiceanu

Constraint

$𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗 (𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

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

Restrictions

𝙽 \geq 1

𝙽 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

$𝙽$ is equal to the number of times that the following conjunctions of constraints hold:

$X_{i} 𝙲𝚃𝚁 X_{i + 1} \land X_{i} \neq X_{i + 1}$ ,
$X_{i + 1} = X_{i + 2} \land \dots \land X_{j - 2} = X_{j - 1}$ ,
$X_{j - 1} \neq X_{j} \land X_{j - 1} \neg 𝙲𝚃𝚁 X_{j}$ .

where $X_{k}$ is the $k^{t h}$ item of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection and $1 \leq i, i + 2 \leq j, j \leq n$ and $𝙲𝚃𝚁$ is $<$ or $>$ .

Example

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

The $𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗$ constraint holds since the sequence $11488271$ contains three inflexions peaks that respectively correspond to values 8, 2 and 7.

Figure 5.164.1. The sequence $11488271$ and its three inflexions

Typical

𝙽 > 0

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

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 1

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ can be reversed.
One and the same constant can be added to the $𝚟𝚊𝚛$ attribute of all items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Usage

Useful for constraining the number of inflexions of a sequence of domain variables.

Remark

Since the arity of the arc constraint is not fixed, the $𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗$ constraint cannot be currently described. However, this would not hold anymore if we were introducing a slot that specifies how to merge adjacent vertices of the final graph.

Keywords

characteristic of a constraint: automaton, automaton with counters.

combinatorial object: sequence.

constraint network structure: sliding cyclic(1) constraint network(2).

Automaton: Figure 5.164.2 depicts the automaton associated with the $𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗$ constraint. To each pair of consecutive variables $({𝚅𝙰𝚁}_{i}, {𝚅𝙰𝚁}_{i + 1})$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a signature variable $𝚂_{i}$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ , ${𝚅𝙰𝚁}_{i + 1}$ and $𝚂_{i}$ : $({𝚅𝙰𝚁}_{i} > {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow 𝚂_{i} = 0) \land ({𝚅𝙰𝚁}_{i} = {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow 𝚂_{i} = 1) \land ({𝚅𝙰𝚁}_{i} < {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow 𝚂_{i} = 2)$ .

Figure 5.164.2. Automaton of the $𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗$ constraint

Figure 5.164.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.164. inflexion

Figure 5.164.1. The sequence $11488271$ and its three inflexions

Figure 5.164.2. Automaton of the $𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗$ constraint

Figure 5.164.3. 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.164. inflexion

Figure 5.164.1. The sequence 1 1 4 8 8 2 7 1 and its three inflexions

Figure 5.164.2. Automaton of the 𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗 constraint

Figure 5.164.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗 constraint

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

Figure 5.164.1. The sequence $11488271$ and its three inflexions

Figure 5.164.2. Automaton of the $𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗$ constraint

Figure 5.164.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗$ constraint