5.166. int_value_precede

DESCRIPTIONLINKSAUTOMATON
Origin

[YatChiuLawJimmyLee04]

Constraint

πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ(πš‚,πšƒ,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
πš‚πš’πš—πš
πšƒπš’πš—πš
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš‚β‰ πšƒ
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

If value πšƒ occurs in the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ then its first occurrence should be preceded by an occurrence of value πš‚.

Example
(0,1,4,0,6,1,0)

The πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ constraint holds since the first occurrence of value 0 precedes the first occurrence of value 1.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πšŠπšπš•πšŽπšŠπšœπš(1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš‚)
πšŠπšπš•πšŽπšŠπšœπš(1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšƒ)
Symmetries
  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that is different from πš‚ and πšƒ can be replaced by any other value that is also different from πš‚ and πšƒ.

  • All occurrences of values πš‚ and πšƒ can be swapped in πš‚, πšƒ and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›.

Algorithm

A filtering algorithm for maintaining value precedence is presented inΒ [YatChiuLawJimmyLee04]. Its complexity is linear to the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

See also

generalisation: πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš—Β (πšœπšŽπššπšžπšŽπš—πšŒπšŽ of 2 πšŸπšŠπš•πšžπšŽπšœ replaced by πšœπšŽπššπšžπšŽπš—πšŒπšŽ of at least 2 πšŸπšŠπš•πšžπšŽπšœ), 𝚜𝚎𝚝_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽΒ (πšœπšŽπššπšžπšŽπš—πšŒπšŽ of πšπš˜πš–πšŠπš’πš— πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ replaced by πšœπšŽπššπšžπšŽπš—πšŒπšŽ of 𝚜𝚎𝚝 πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ).

Keywords

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

constraint network structure: Berge-acyclic constraint network.

constraint type: order constraint.

filtering: arc-consistency.

symmetry: symmetry, indistinguishable values, value precedence.

Automaton

FigureΒ 5.166.1 depicts the automaton associated with the πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ constraint. Let πš…π™°πš i be the i th variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. To each triple (πš‚,πšƒ,πš…π™°πš i ) corresponds a signature variable πš‚ i as well as the following signature constraint: (πš…π™°πš i =πš‚β‡”πš‚ i =1)∧(πš…π™°πš i =πšƒβ‡”πš‚ i =2)∧(πš…π™°πš i β‰ πš‚βˆ§πš…π™°πš i β‰ πšƒβ‡”πš‚ i =3).

Figure 5.166.1. Automaton of the πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ constraint
ctrs/int_value_precede1
Figure 5.166.2. Hypergraph of the reformulation corresponding to the automaton of the πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ constraint
ctrs/int_value_precede2