5.374. stage_element

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Choco, derived from πšŽπš•πšŽπš–πšŽπš—πš.

Constraint

𝚜𝚝𝚊𝚐𝚎_πšŽπš•πšŽπš–πšŽπš—πš(π™Έπšƒπ™΄π™Ό,πšƒπ™°π™±π™»π™΄)

Usual name

𝚜𝚝𝚊𝚐𝚎_πšŽπš•πš

Synonym

𝚜𝚝𝚊𝚐𝚎_πšŽπš•πšŽπš–.

Arguments
π™Έπšƒπ™΄π™ΌπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πšπšŸπšŠπš›,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›)
πšƒπ™°π™±π™»π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš•πš˜πš -πš’πš—πš,πšžπš™-πš’πš—πš,πšŸπšŠπš•πšžπšŽ-πš’πš—πš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπšƒπ™΄π™Ό,[πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ])
|π™Έπšƒπ™΄π™Ό|=1
|πšƒπ™°π™±π™»π™΄|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°π™±π™»π™΄,[πš•πš˜πš ,πšžπš™,πšŸπšŠπš•πšžπšŽ])
πšƒπ™°π™±π™»π™΄.πš•πš˜πš β‰€πšƒπ™°π™±π™»π™΄.πšžπš™
πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_𝚜𝚎𝚚(πšƒπ™°π™±π™»π™΄,[πš•πš˜πš ])
Purpose

Let πš•πš˜πš  i , πšžπš™ i and πšŸπšŠπš•πšžπšŽ i respectively denote the values of the πš•πš˜πš , πšžπš™ and πšŸπšŠπš•πšžπšŽ attributes of the i th item of the πšƒπ™°π™±π™»π™΄ collection. First we have that: πš•πš˜πš  i β‰€πšžπš™ i and πšžπš™ i +1=πš•πš˜πš  i+1 .

Second, the 𝚜𝚝𝚊𝚐𝚎_πšŽπš•πšŽπš–πšŽπš—πš constraint forces the following equivalence:

πš•πš˜πš  i β‰€π™Έπšƒπ™΄π™Ό.πš’πš—πšπšŽπš‘βˆ§π™Έπšƒπ™΄π™Ό.πš’πš—πšπšŽπš‘β‰€πšžπš™ i β‡”π™Έπšƒπ™΄π™Ό.πšŸπšŠπš•πšžπšŽ=πšŸπšŠπš•πšžπšŽ i .

Example
πš’πš—πšπšŽπš‘-5 πšŸπšŠπš•πšžπšŽ-6,πš•πš˜πš -3πšžπš™-7πšŸπšŠπš•πšžπšŽ-6,πš•πš˜πš -8πšžπš™-8πšŸπšŠπš•πšžπšŽ-8,πš•πš˜πš -9πšžπš™-14πšŸπšŠπš•πšžπšŽ-2,πš•πš˜πš -15πšžπš™-19πšŸπšŠπš•πšžπšŽ-9

FigureΒ 5.374.1 depicts the function associated with the items of the πšƒπ™°π™±π™»π™΄ collection. The 𝚜𝚝𝚊𝚐𝚎_πšŽπš•πšŽπš–πšŽπš—πš constraint holds since:

  • The value of π™Έπšƒπ™΄π™Ό[1].πš’πš—πšπšŽπš‘ is located between the values of the πš•πš˜πš  and πšžπš™ attributes of the first item of the πšƒπ™°π™±π™»π™΄ collection (i.e.,Β 5∈[3,7]).

  • The value of π™Έπšƒπ™΄π™Ό[1].πšŸπšŠπš•πšžπšŽ corresponds to the πšŸπšŠπš•πšžπšŽ attribute of the first item of the πšƒπ™°π™±π™»π™΄ collection (i.e.,Β 6).

Figure 5.374.1. Function defined on four intervals β‘ , β‘‘, β‘’ and β‘£ associated with the πšƒπ™°π™±π™»π™΄ collection of the Example slot for linking the πš’πš—πšπšŽπš‘ and πšŸπšŠπš•πšžπšŽ attributes of the π™Έπšƒπ™΄π™Ό collection
ctrs/stage_element-1-tikz
Typical
|πšƒπ™°π™±π™»π™΄|>1
πš›πšŠπš—πšπšŽ(πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ)>1
πšƒπ™°π™±π™»π™΄.πš•πš˜πš <πšƒπ™°π™±π™»π™΄.πšžπš™
Symmetry

All occurrences of two distinct values in π™Έπšƒπ™΄π™Ό.πšŸπšŠπš•πšžπšŽ or πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ can be swapped; all occurrences of a value in π™Έπšƒπ™΄π™Ό.πšŸπšŠπš•πšžπšŽ or πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ can be renamed to any unused value.

Arg. properties
  • Functional dependency: π™Έπšƒπ™΄π™Ό.πšŸπšŠπš•πšžπšŽ determined by π™Έπšƒπ™΄π™Ό.πš’πš—πšπšŽπš‘ and πšƒπ™°π™±π™»π™΄.

  • Suffix-extensible wrt. πšƒπ™°π™±π™»π™΄.

See also

common keyword: πšŽπš•πšŽπš–, πšŽπš•πšŽπš–πšŽπš—πšΒ (data constraint).

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

constraint arguments: binary constraint, pure functional dependency.

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

constraint type: data constraint.

filtering: arc-consistency.

modelling: table, functional dependency.

Arc input(s)

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

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšŠπš‹πš•πšŽ1,πšπšŠπš‹πš•πšŽ2)

Arc arity
Arc constraint(s)
β€’ πšπšŠπš‹πš•πšŽ1.πš•πš˜πš β‰€πšπšŠπš‹πš•πšŽ1.πšžπš™
β€’ πšπšŠπš‹πš•πšŽ1.πšžπš™+1=πšπšŠπš‹πš•πšŽ2.πš•πš˜πš 
β€’ πšπšŠπš‹πš•πšŽ2.πš•πš˜πš β‰€πšπšŠπš‹πš•πšŽ2.πšžπš™
Graph property(ies)
𝐍𝐀𝐑𝐂=|πšƒπ™°π™±π™»π™΄|-1

Arc input(s)

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

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

Arc arity
Arc constraint(s)
β€’ πš’πšπšŽπš–.πš’πš—πšπšŽπš‘β‰₯πšπšŠπš‹πš•πšŽ.πš•πš˜πš 
β€’ πš’πšπšŽπš–.πš’πš—πšπšŽπš‘β‰€πšπšŠπš‹πš•πšŽ.πšžπš™
β€’ πš’πšπšŽπš–.πšŸπšŠπš•πšžπšŽ=πšπšŠπš‹πš•πšŽ.πšŸπšŠπš•πšžπšŽ
Graph property(ies)
𝐍𝐀𝐑𝐂=1

Graph model

The first graph constraint models the restrictions on the πš•πš˜πš  and πšžπš™ attributes of the πšƒπ™°π™±π™»π™΄ collection, while the second graph constraint is similar to the one used for defining the πšŽπš•πšŽπš–πšŽπš—πš constraint.

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

Figure 5.374.2. Initial and final graph of the 𝚜𝚝𝚊𝚐𝚎_πšŽπš•πšŽπš–πšŽπš—πš constraint
ctrs/stage_elementActrs/stage_elementB
(a) (b)
Automaton

FigureΒ 5.374.3 depicts the automaton associated with the 𝚜𝚝𝚊𝚐𝚎_πšŽπš•πšŽπš–πšŽπš—πš constraint. Let π™Έπ™½π™³π™΄πš‡ and πš…π™°π™»πš„π™΄ respectively be the πš’πš—πšπšŽπš‘ and the πšŸπšŠπš•πšžπšŽ attributes of the unique item of the π™Έπšƒπ™΄π™Ό collection. Let π™»π™Ύπš† i , πš„π™Ώ i and πš…π™°π™»πš„π™΄ i respectively be the πš•πš˜πš , the πšžπš™ and the πšŸπšŠπš•πšžπšŽ attributes of the i th item of the πšƒπ™°π™±π™»π™΄ collection. To each quintuple (π™Έπ™½π™³π™΄πš‡,πš…π™°π™»πš„π™΄,π™»π™Ύπš† i ,πš„π™Ώ i ,πš…π™°π™»πš„π™΄ i ) corresponds a 0-1 signature variable S i as well as the following signature constraint: ((π™»π™Ύπš† i β‰€π™Έπ™½π™³π™΄πš‡)∧(π™Έπ™½π™³π™΄πš‡β‰€πš„π™Ώ i )∧(πš…π™°π™»πš„π™΄=πš…π™°π™»πš„π™΄ i ))⇔S i .

Figure 5.374.3. Automaton of the 𝚜𝚝𝚊𝚐𝚎_πšŽπš•πšŽπš–πšŽπš—πš constraint
ctrs/stage_element-2-tikz
Figure 5.374.4. Hypergraph of the reformulation corresponding to the automaton of the 𝚜𝚝𝚊𝚐𝚎_πšŽπš•πšŽπš–πšŽπš—πš constraint
ctrs/stage_element-3-tikz