## 5.193. inflexion

Origin

N. Beldiceanu

Constraint

$\mathrm{𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗}\left(𝙽,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Arguments
 $𝙽$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $𝙽\ge 0$ $𝙽\le \mathrm{𝚖𝚊𝚡}\left(0,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-2\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

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

• ${X}_{i}\mathrm{𝙲𝚃𝚁}{X}_{i+1}\wedge {X}_{i}\ne {X}_{i+1}$,

• ${X}_{i+1}={X}_{i+2}\wedge \cdots \wedge {X}_{j-2}={X}_{j-1}$,

• ${X}_{j-1}\ne {X}_{j}\wedge {X}_{j-1}¬\mathrm{𝙲𝚃𝚁}{X}_{j}$.

where ${X}_{k}$ is the ${k}^{th}$ item of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection and $1\le i$, $i+2\le j$, $j\le n$ and $\mathrm{𝙲𝚃𝚁}$ is $<$ or $>$.

Example
 $\left(3,〈1,1,4,8,8,2,7,1〉\right)$ $\left(0,〈1,1,4,4,6,6,7,9〉\right)$ $\left(7,〈1,0,2,0,7,2,7,1,2〉\right)$

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

All solutions

Figure 5.193.2 gives all solutions to the following non ground instance of the $\mathrm{𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗}$ constraint: $𝙽\in \left\{0,2\right\}$, ${V}_{1}=2$, ${V}_{2}\in \left[2,3\right]$, ${V}_{3}\in \left[1,2\right]$, ${V}_{4}\in \left[1,2\right]$, ${V}_{5}=3$, $\mathrm{𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗}$$\left(𝙽,〈{V}_{1},{V}_{2},{V}_{3},{V}_{4},{V}_{5}〉\right)$.

Typical
 $𝙽>0$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>2$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ can be reversed.

• One and the same constant can be added to the $\mathrm{𝚟𝚊𝚛}$ attribute of all items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Arg. properties

Functional dependency: $𝙽$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

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 $\mathrm{𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗}$ constraint cannot be currently described with the graph-based representation. However, this would not hold anymore if we were introducing a slot that specifies how to merge adjacent vertices of the final graph.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 9 64 625 7776 117649 2097152 43046721

Number of solutions for $\mathrm{𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗}$: domains $0..n$

Length ($n$)2345678
Total9646257776117649209715243046721
 Parameter value

09361354981841685625731
1-28320258818494125284828120
2--1703348440584923205069970
3---13424044677893612341184
4----1281054915214547186
5-----1446048354520
6------1880010

Solution count for $\mathrm{𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗}$: domains $0..n$

Keywords
Cond. implications

$•$ $\mathrm{𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗}\left(𝙽,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

with  $𝙽>0$

implies $\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$$\left(\mathrm{𝙽𝚅𝙰𝙻},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

when  $\mathrm{𝙽𝚅𝙰𝙻}=2$.

$•$ $\mathrm{𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗}\left(𝙽,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

with  $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)=0$

implies $\mathrm{𝚙𝚎𝚊𝚔}$$\left(𝙽,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$.

$•$ $\mathrm{𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗}\left(𝙽,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

with  $\mathrm{𝚙𝚎𝚊𝚔}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)=0$

implies $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$$\left(𝙽,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$.

Automaton

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