5.195. lex_different

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Used for defining πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Constraint

πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš(πš…π™΄π™²πšƒπ™Ύπš1,πš…π™΄π™²πšƒπ™Ύπš2)

Synonyms

πšπš’πšπšπšŽπš›πšŽπš—πš, πšπš’πšπš.

Arguments
πš…π™΄π™²πšƒπ™Ύπš1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™΄π™²πšƒπ™Ύπš2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš2,πšŸπšŠπš›)
|πš…π™΄π™²πšƒπ™Ύπš1|>0
|πš…π™΄π™²πšƒπ™Ύπš1|=|πš…π™΄π™²πšƒπ™Ύπš2|
Purpose

Vectors πš…π™΄π™²πšƒπ™Ύπš1 and πš…π™΄π™²πšƒπ™Ύπš2 differ in at least one component.

Example
5,2,7,1,5,3,7,1

The πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš constraint holds since πš…π™΄π™²πšƒπ™Ύπš1= 〈5,2,7,1βŒͺ and πš…π™΄π™²πšƒπ™Ύπš2= 〈5,3,7,1βŒͺ differ in their second component.

Symmetries
  • Arguments are permutable w.r.t. permutation (πš…π™΄π™²πšƒπ™Ύπš1,πš…π™΄π™²πšƒπ™Ύπš2).

  • Items of πš…π™΄π™²πšƒπ™Ύπš1 and πš…π™΄π™²πšƒπ™Ύπš2 are permutable (same permutation used).

Reformulation

The πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš(βŒ©πšŸπšŠπš›-U 1 ,πšŸπšŠπš›-U 2 ,...,πšŸπšŠπš›-U |πš…π™΄π™²πšƒπ™Ύπš1| βŒͺ,βŒ©πšŸπšŠπš›-V 1 ,πšŸπšŠπš›-V 2 ,...,πšŸπšŠπš›-V |πš…π™΄π™²πšƒπ™Ύπš2| βŒͺ) constraint can be expressed in term of the following disjunction of disequality constraints U 1 β‰ V 1 ∨U 2 β‰ V 2 ∨...∨U |πš…π™΄π™²πšƒπ™Ύπš1| β‰ V |πš…π™΄π™²πšƒπ™Ύπš2| .

Used in

πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

See also

common keyword: πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš, πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπššΒ (vector).

implied by: πšπš’πšœπš“πš˜πš’πš—πš, πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›, πš•πšŽπš‘_πš•πšŽπšœπšœ.

negation: πš•πšŽπš‘_πšŽπššπšžπšŠπš•.

system of constraints: πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Keywords

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

constraint network structure: Berge-acyclic constraint network.

filtering: arc-consistency.

Arc input(s)

πš…π™΄π™²πšƒπ™Ύπš1 πš…π™΄π™²πšƒπ™Ύπš2

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡(=)β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŽπšŒπšπš˜πš›1,πšŸπšŽπšŒπšπš˜πš›2)

Arc arity
Arc constraint(s)
πšŸπšŽπšŒπšπš˜πš›1.πšŸπšŠπš›β‰ πšŸπšŽπšŒπšπš˜πš›2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂β‰₯1

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.195.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the unique arc of the final graph is stressed in bold. It corresponds to a component where the two vectors differ.

Figure 5.195.1. Initial and final graph of the πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš constraint
ctrs/lex_differentActrs/lex_differentB
(a) (b)
Automaton

FigureΒ 5.195.2 depicts the automaton associated with the πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš constraint. Let πš…π™°πš1 i and πš…π™°πš2 i respectively be the πšŸπšŠπš› attributes of the i th items of the πš…π™΄π™²πšƒπ™Ύπš1 and the πš…π™΄π™²πšƒπ™Ύπš2 collections. To each pair (πš…π™°πš1 i ,πš…π™°πš2 i ) corresponds a 0-1 signature variable πš‚ i as well as the following signature constraint: πš…π™°πš1 i =πš…π™°πš2 i β‡”πš‚ i .

Figure 5.195.2. Automaton of the πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš constraint
ctrs/lex_different1
Figure 5.195.3. Hypergraph of the reformulation corresponding to the automaton of the πš•πšŽπš‘_πšπš’πšπšπšŽπš›πšŽπš—πš constraint
ctrs/lex_different2