5.164. inflexion

DESCRIPTIONLINKSAUTOMATON
Origin

N.Β Beldiceanu

Constraint

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

Arguments
π™½πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
𝙽β‰₯1
𝙽≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
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

The πš’πš—πšπš•πšŽπš‘πš’πš˜πš— 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.164.1. The sequence 1 1 4 8 8 2 7 1 and its three inflexions
ctrs/inflexion1
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.

See also

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

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 β‡”πš‚ i =0) ∧ (πš…π™°πš i =πš…π™°πš i+1 β‡”πš‚ i =1) ∧ (πš…π™°πš i <πš…π™°πš i+1 β‡”πš‚ i =2).

Figure 5.164.2. Automaton of the πš’πš—πšπš•πšŽπš‘πš’πš˜πš— constraint
ctrs/inflexion2
Figure 5.164.3. Hypergraph of the reformulation corresponding to the automaton of the πš’πš—πšπš•πšŽπš‘πš’πš˜πš— constraint
ctrs/inflexion3