5.193. inflexion

DESCRIPTIONLINKSAUTOMATON
Origin

N.Β Beldiceanu

Constraint

πš’πš—πšπš•πšŽπš‘πš’πš˜πš—(𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™½πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
𝙽β‰₯0
π™½β‰€πš–πšŠπš‘(0,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-2)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

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

  • X i π™²πšƒπš X i+1 ∧X i β‰ X i+1 ,

  • X i+1 =X i+2 βˆ§β‹―βˆ§X j-2 =X j-1 ,

  • X j-1 β‰ X j ∧X j-1 Β¬π™²πšƒπš X j .

where X k is the k th item of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection and 1≀i, i+2≀j, j≀n and π™²πšƒπš is < or >.

Example
(3,1,1,4,8,8,2,7,1)
(0,1,1,4,4,6,6,7,9)
(7,1,0,2,0,7,2,7,1,2)

The first πš’πš—πšπš•πšŽπš‘πš’πš˜πš— constraint holds since the sequence 1 1 4 8 8 2 7 1 contains three inflexions peaks that respectively correspond to values 8, 2 and 7.

Figure 5.193.1. Illustration of the first example of the Example slot: a sequence of eight variables V 1 , V 2 , V 3 , V 4 , V 5 , V 6 , V 7 , V 8 respectively fixed to values 1, 1, 4, 8, 8, 2, 7, 1 and its three inflexions in red, two peaks and one valley (𝙽=3)
ctrs/inflexion-1-tikz
All solutions

FigureΒ 5.193.2 gives all solutions to the following non ground instance of the πš’πš—πšπš•πšŽπš‘πš’πš˜πš— constraint: π™½βˆˆ{0,2}, V 1 =2, V 2 ∈[2,3], V 3 ∈[1,2], V 4 ∈[1,2], V 5 =3, πš’πš—πšπš•πšŽπš‘πš’πš˜πš—(𝙽,〈V 1 ,V 2 ,V 3 ,V 4 ,V 5 βŒͺ).

Figure 5.193.2. All solutions corresponding to the non ground example of the πš’πš—πšπš•πšŽπš‘πš’πš˜πš— constraint of the All solutions slot where each inflexion (i.e.Β peak or valley) is coloured in orange or cyan
ctrs/inflexion-2-tikz
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 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Arg. properties

Functional dependency: 𝙽 determined by πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

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 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)2345678
Solutions9646257776117649209715243046721

Number of solutions for πš’πš—πšπš•πšŽπš‘πš’πš˜πš—: domains 0..n

ctrs/inflexion-3-tikz

ctrs/inflexion-4-tikz

Length (n)2345678
Total9646257776117649209715243046721
Parameter
value

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

Solution count for πš’πš—πšπš•πšŽπš‘πš’πš˜πš—: domains 0..n

ctrs/inflexion-5-tikz

ctrs/inflexion-6-tikz

See also

common keyword: πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’, πš–πš’πš—_πšπš’πšœπš_πš‹πšŽπšπš πšŽπšŽπš—_πš’πš—πšπš•πšŽπš‘πš’πš˜πš—, πš™πšŽπšŠπš”, πšŸπšŠπš•πš•πšŽπš’Β (sequence).

Keywords

characteristic of a constraint: automaton, automaton with counters, automaton with same input symbol.

combinatorial object: sequence.

constraint arguments: reverse of a constraint, pure functional dependency.

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

filtering: glue matrix.

modelling: functional dependency.

Cond. implications

β€’ πš’πš—πšπš•πšŽπš‘πš’πš˜πš—(𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Β Β Β  withΒ  𝙽>0

Β Β implies πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŠπš•πšžπšŽ(π™½πš…π™°π™»,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Β Β Β  whenΒ  π™½πš…π™°π™»=2.

β€’ πš’πš—πšπš•πšŽπš‘πš’πš˜πš—(𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Β Β Β  withΒ  πšŸπšŠπš•πš•πšŽπš’(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)=0

Β Β implies πš™πšŽπšŠπš”(𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚).

β€’ πš’πš—πšπš•πšŽπš‘πš’πš˜πš—(𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Β Β Β  withΒ  πš™πšŽπšŠπš”(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)=0

Β Β implies πšŸπšŠπš•πš•πšŽπš’(𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚).

Automaton

FigureΒ 5.193.3 depicts the automaton associated with the πš’πš—πšπš•πšŽπš‘πš’πš˜πš— constraint. To each pair of consecutive variables (πš…π™°πš i ,πš…π™°πš i+1 ) of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable S i . The following signature constraint links πš…π™°πš i , πš…π™°πš i+1 and S i : (πš…π™°πš i <πš…π™°πš i+1 ⇔S i =0) ∧ (πš…π™°πš i =πš…π™°πš i+1 ⇔S i =1) ∧ (πš…π™°πš i >πš…π™°πš i+1 ⇔S i =2).

Figure 5.193.3. Automaton of the πš’πš—πšπš•πšŽπš‘πš’πš˜πš— constraint (state s means that we are in stationary mode, state i means that we are in increasing mode, state j means that we are in decreasing mode, a new inflexion is detected each time we switch from increasing to decreasing mode – or conversely from decreasing to increasing mode – and the counter C is incremented accordingly)
ctrs/inflexion-7-tikz
Figure 5.193.4. Hypergraph of the reformulation corresponding to the automaton of the πš’πš—πšπš•πšŽπš‘πš’πš˜πš— constraint
ctrs/inflexion-8-tikz
Figure 5.193.5. Glue matrix associated with the automaton of the πš’πš—πšπš•πšŽπš‘πš’πš˜πš— constraint
s = * i <{<|=} * j >{>|=} *

s = *

Β Β Β 0

ctrs/inflexion-10-tikz

Β Β Β C ←

ctrs/inflexion-11-tikz

Β Β Β C ←

ctrs/inflexion-12-tikz

i <{<|=} *

Β Β Β C β†’

ctrs/inflexion-13-tikz

C β†’+1+C ←

ctrs/inflexion-14-tikz

C β†’+C ←

ctrs/inflexion-15-tikz

j >{>|=} *

Β Β Β C β†’

ctrs/inflexion-16-tikz

C β†’+C ←

ctrs/inflexion-17-tikz

C β†’+1+C ←

ctrs/inflexion-18-tikz

ctrs/inflexion-9-tikz
Figure 5.193.6. Illustrating the use of the state pair (j,j) of the glue matrix for linking 𝙽 with the counters variables obtained after reading the prefix 1,1,4,8,8,2 and corresponding suffix 2,7,1 of the sequence 1,1,4,8,8,2,7,1; note that the suffix 2,7,1 (in pink) is proceed in reverse order; the left (resp.Β right) table shows the initialisation (for i=0) and the evolution (for i>0) of the state of the automaton and its counter C upon reading the prefix 1,1,4,8,8,2 (resp.Β the reverse suffix 1,7,2).
ctrs/inflexion-19-tikz