5.227. next_element

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

N.Β Beldiceanu

Constraint

πš—πšŽπš‘πš_πšŽπš•πšŽπš–πšŽπš—πš(πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³,π™Έπ™½π™³π™΄πš‡,πšƒπ™°π™±π™»π™΄,πš…π™°π™»)

Arguments
πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³πšπšŸπšŠπš›
π™Έπ™½π™³π™΄πš‡πšπšŸπšŠπš›
πšƒπ™°π™±π™»π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›)
πš…π™°π™»πšπšŸπšŠπš›
Restrictions
π™Έπ™½π™³π™΄πš‡β‰₯1
π™Έπ™½π™³π™΄πš‡β‰€|πšƒπ™°π™±π™»π™΄|
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°π™±π™»π™΄,[πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ])
πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘β‰₯1
πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘β‰€|πšƒπ™°π™±π™»π™΄|
πšπš’πšœπšπš’πš—πšŒπš(πšƒπ™°π™±π™»π™΄,πš’πš—πšπšŽπš‘)
Purpose

π™Έπ™½π™³π™΄πš‡ is the smallest entry of πšƒπ™°π™±π™»π™΄ strictly greater than πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³ containing value πš…π™°π™».

Example
2,3,πš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-1,πš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-8,πš’πš—πšπšŽπš‘-3πšŸπšŠπš•πšžπšŽ-9,πš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-5,πš’πš—πšπšŽπš‘-5πšŸπšŠπš•πšžπšŽ-9,9

The πš—πšŽπš‘πš_πšŽπš•πšŽπš–πšŽπš—πš constraint holds since 3 is the smallest entry located after entry 2 that contains value 9.

Symmetry

Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

Usage

Originally introduced for modelling the fact that a nucleotide has to be consumed as soon as possible at cycle π™Έπ™½π™³π™΄πš‡ after a given cycle represented by variable πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³.

See also

related: πš–πš’πš—πš’πš–πšžπš–_πšπš›πšŽπšŠπšπšŽπš›_πšπš‘πšŠπš—Β (identify an element in a table), πš—πšŽπš‘πš_πšπš›πšŽπšŠπšπšŽπš›_πšŽπš•πšŽπš–πšŽπš—πšΒ (allow to iterate over the values of a table).

Keywords

characteristic of a constraint: minimum, automaton, automaton without counters, reified automaton constraint, derived collection.

constraint network structure: centered cyclic(3) constraint network(1).

constraint type: data constraint.

modelling: table.

Derived Collection
πšŒπš˜πš•π™Έπšƒπ™΄π™Ό-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πšπšŸπšŠπš›,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›),πš’πšπšŽπš–(πš’πš—πšπšŽπš‘-πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³,πšŸπšŠπš•πšžπšŽ-πš…π™°π™»)]
Arc input(s)

π™Έπšƒπ™΄π™Ό πšƒπ™°π™±π™»π™΄

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš–,πšπšŠπš‹πš•πšŽ)

Arc arity
Arc constraint(s)
β€’ πš’πšπšŽπš–.πš’πš—πšπšŽπš‘<πšπšŠπš‹πš•πšŽ.πš’πš—πšπšŽπš‘
β€’ πš’πšπšŽπš–.πšŸπšŠπš•πšžπšŽ=πšπšŠπš‹πš•πšŽ.πšŸπšŠπš•πšžπšŽ
Graph property(ies)
𝐍𝐀𝐑𝐂>0

Sets
π–²π–΄π–’π–’β†¦πšœπš˜πšžπš›πšŒπšŽ,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ-πšŒπš˜πš•πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),πš’πšπšŽπš–(πšŸπšŠπš›-πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘)]

Constraint(s) on sets
πš–πš’πš—πš’πš–πšžπš–(π™Έπ™½π™³π™΄πš‡,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)
Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.227.1 respectively show the initial and final graph associated with the second graph constraint of the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the arcs of the final graph are stressed in bold.

Figure 5.227.1. Initial and final graph of the πš—πšŽπš‘πš_πšŽπš•πšŽπš–πšŽπš—πš constraint
ctrs/next_elementActrs/next_elementB
(a) (b)
Automaton

FigureΒ 5.227.2 depicts the automaton associated with the πš—πšŽπš‘πš_πšŽπš•πšŽπš–πšŽπš—πš constraint. Let 𝙸 k and πš… k respectively be the πš’πš—πšπšŽπš‘ and the πšŸπšŠπš•πšžπšŽ attributes of the k th item of the πšƒπ™°π™±π™»π™΄ collections. To each quintuple (πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³,π™Έπ™½π™³π™΄πš‡,πš…π™°π™»,𝙸 k ,πš… k ) corresponds a signature variable πš‚ k as well as the following signature constraint:

((𝙸 k β‰€πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k <π™Έπ™½π™³π™΄πš‡)∧(πš… k =πš…π™°π™»))β‡”πš‚ k =0 ∧

((𝙸 k β‰€πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k <π™Έπ™½π™³π™΄πš‡)∧(πš… k β‰ πš…π™°π™»))β‡”πš‚ k =1 ∧

((𝙸 k β‰€πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k =π™Έπ™½π™³π™΄πš‡)∧(πš… k =πš…π™°π™»))β‡”πš‚ k =2 ∧

((𝙸 k β‰€πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k =π™Έπ™½π™³π™΄πš‡)∧(πš… k β‰ πš…π™°π™»))β‡”πš‚ k =3 ∧

((𝙸 k β‰€πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k >π™Έπ™½π™³π™΄πš‡)∧(πš… k =πš…π™°π™»))β‡”πš‚ k =4 ∧

((𝙸 k β‰€πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k >π™Έπ™½π™³π™΄πš‡)∧(πš… k β‰ πš…π™°π™»))β‡”πš‚ k =5 ∧

((𝙸 k >πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k <π™Έπ™½π™³π™΄πš‡)∧(πš… k =πš…π™°π™»))β‡”πš‚ k =6 ∧

((𝙸 k >πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k <π™Έπ™½π™³π™΄πš‡)∧(πš… k β‰ πš…π™°π™»))β‡”πš‚ k =7 ∧

((𝙸 k >πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k =π™Έπ™½π™³π™΄πš‡)∧(πš… k =πš…π™°π™»))β‡”πš‚ k =8 ∧

((𝙸 k >πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k =π™Έπ™½π™³π™΄πš‡)∧(πš… k β‰ πš…π™°π™»))β‡”πš‚ k =9 ∧

((𝙸 k >πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k >π™Έπ™½π™³π™΄πš‡)∧(πš… k =πš…π™°π™»))β‡”πš‚ k =10 ∧

((𝙸 k >πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³)∧(𝙸 k >π™Έπ™½π™³π™΄πš‡)∧(πš… k β‰ πš…π™°π™»))β‡”πš‚ k =11.

The automaton is constructed in order to fulfil the following conditions:

  • We look for an item of the πšƒπ™°π™±π™»π™΄ collection such that π™Έπ™½π™³π™΄πš‡ i >πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³ and π™Έπ™½π™³π™΄πš‡ i =π™Έπ™½π™³π™΄πš‡ and πš…π™°π™»πš„π™΄ i =πš…π™°π™»,

  • There should not exist any item of the πšƒπ™°π™±π™»π™΄ collection such that π™Έπ™½π™³π™΄πš‡ i >πšƒπ™·πšπ™΄πš‚π™·π™Ύπ™»π™³ and π™Έπ™½π™³π™΄πš‡ i <π™Έπ™½π™³π™΄πš‡ and πš…π™°π™»πš„π™΄ i =πš…π™°π™».

Figure 5.227.2. Automaton of the πš—πšŽπš‘πš_πšŽπš•πšŽπš–πšŽπš—πš constraint
ctrs/next_element1
Figure 5.227.3. Hypergraph of the reformulation corresponding to the automaton of the πš—πšŽπš‘πš_πšŽπš•πšŽπš–πšŽπš—πš constraint
ctrs/next_element2