5.261. min_width_valley

DESCRIPTIONLINKSAUTOMATON
Origin

derived from πšŸπšŠπš•πš•πšŽπš’

Constraint

πš–πš’πš—_πš πš’πšπšπš‘_πšŸπšŠπš•πš•πšŽπš’(𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™·,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonym

πš–πš’πš—_πš‹πšŠπšœπšŽ_πšŸπšŠπš•πš•πšŽπš’.

Arguments
𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™·πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™·β‰₯0
𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™·β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-2
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

Given a sequence πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ constraint 𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· to be fixed to the width of the smallest valley, or to 0 if no valley exists.

Example
(5,3,3,5,5,4,2,2,3,4,6,6,5,5,5,5,5,5,6)
(0,3,8,8,5,0,0)
(4,9,8,8,0,0,2)

The first πš–πš’πš—_πš πš’πšπšπš‘_πšŸπšŠπš•πš•πšŽπš’ constraint holds since the sequence 3 3 5 5 4 2 2 3 4 6 6 5 5 5 5 5 5 6 contains two valleys of respective width 5 and 6 (see FigureΒ 5.261.1) and since its argument 𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· is fixed to the smallest value 5.

Figure 5.261.1. Illustration of the first example of the Example slot: a sequence of eighteen variables V 1 , V 2 , V 3 , V 4 , V 5 , V 6 , V 7 , V 8 , V 9 , V 10 , V 11 , V 12 , V 13 , V 14 , V 15 , V 16 , V 17 , V 18 respectively fixed to values 3, 3, 5, 5, 4, 2, 2, 3, 4, 6, 6, 5, 5, 5, 5, 5, 5, 6 and its two valleys of width 5 and 6.
ctrs/min_width_valley-1-tikz
Typical
𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™·>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
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 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Counting
Length (n)2345678
Solutions9646257776117649209715243046721

Number of solutions for πš–πš’πš—_πš πš’πšπšπš‘_πšŸπšŠπš•πš•πšŽπš’: domains 0..n

ctrs/min_width_valley-2-tikz

ctrs/min_width_valley-3-tikz

Length (n)2345678
Total9646257776117649209715243046721
Parameter
value

095029517921108869498439791
1-14230320556637117439826327058
2--1002100284204249289363060
3---679170242687223413256
4----44801304522345982
5-----29154968946
6------188628

Solution count for πš–πš’πš—_πš πš’πšπšπš‘_πšŸπšŠπš•πš•πšŽπš’: domains 0..n

ctrs/min_width_valley-4-tikz

ctrs/min_width_valley-5-tikz

See also

common keyword: πšŸπšŠπš•πš•πšŽπš’Β (sequence).

Keywords

characteristic of a constraint: automaton, automaton with counters.

combinatorial object: sequence.

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

filtering: glue matrix.

modelling: functional dependency.

Automaton

FigureΒ 5.261.2 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.261.2. Automaton of the πš–πš’πš—_πš πš’πšπšπš‘_πšŸπšŠπš•πš•πšŽπš’ constraint: the start of the first potential valley is discovered while triggering the transition from s to j, the bottom of a valley is discovered while triggering the transition from j to k, the end of a valley and the start of the next potential valley are discovered while triggering the transition from k to j; the counters W, C and F respectively stand for min_width, current and first.
ctrs/min_width_valley-6-tikz
Figure 5.261.3. Glue matrix associated with the automaton of the πš–πš’πš—_πš πš’πšπšπš‘_πšŸπšŠπš•πš•πšŽπš’ constraint, where n stands for |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
s {<|=} * j >{>|=} * k <{<|=} *

s {<|=} *

Β Β Β Β 0

𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· ←

𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· ←

j >{>|=} *

𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· β†’

minW β†’,n-F β†’-F ←,W ←

min𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· β†’,n-F β†’-F ←,𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· ←

k <{<|=} *

𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· β†’

min𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· β†’,n-F β†’-F ←,𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· ←

min𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· β†’,𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· ←

ctrs/min_width_valley-7-tikz
Figure 5.261.4. Illustrating the use of the state pair (j,j) of the glue matrix for linking 𝙼𝙸𝙽_πš†π™Έπ™³πšƒπ™· with the counters variables obtained after reading the prefix 6,4,3,1 and corresponding suffix 1,2,5,6 of the sequence 6,4,3,1,2,5,6; note that the suffix 1,2,5,6 (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 counters W, C and F upon reading the prefix 6,4,3,1 (resp.Β the reverse suffix 6,5,2,1).
ctrs/min_width_valley-8-tikz
Figure 5.261.5. Hypergraph of the reformulation corresponding to the automaton of the πš–πš’πš—_πš πš’πšπšπš‘_πšŸπšŠπš•πš•πšŽπš’ constraint
ctrs/min_width_valley-9-tikz