5.196. lex_equal

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Initially introduced for defining πš—πšŸπšŽπšŒπšπš˜πš›

Constraint

πš•πšŽπš‘_πšŽπššπšžπšŠπš•(πš…π™΄π™²πšƒπ™Ύπš1,πš…π™΄π™²πšƒπ™Ύπš2)

Synonyms

πšŽπššπšžπšŠπš•, 𝚎𝚚.

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

πš…π™΄π™²πšƒπ™Ύπš1 is equal to πš…π™΄π™²πšƒπ™Ύπš2. Given two vectors, X β†’ and Y β†’ of n components, 〈X 0 ,...,X n-1 βŒͺ and 〈Y 0 ,...,Y n-1 βŒͺ, X β†’ is equal to Y β†’ if and only if n=0 or X 0 =Y 0 ∧X 1 =Y 1 ∧...∧X n-1 =Y n-1 .

Example
1,9,1,5,1,9,1,5

The πš•πšŽπš‘_πšŽπššπšžπšŠπš• constraint holds since (1)Β the first component of the first vector is equal to the first component of the second vector, (2)Β the second component of the first vector is equal to the second component of the second vector, (3)Β the third component of the first vector is equal to the third component of the second vector and (4)Β the fourth component of the first vector is equal to the fourth component of the second vector.

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

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

Used in

πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŽπšŒπšπš˜πš›, πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš›, πš—πšŸπšŽπšŒπšπš˜πš›, πš—πšŸπšŽπšŒπšπš˜πš›πšœ.

See also

common keyword: πš—πšŸπšŽπšŒπšπš˜πš›Β (vector).

implied by: 𝚟𝚎𝚌_𝚎𝚚_πšπšžπš™πš•πšŽ.

implies: πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš, πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš, πšœπšŠπš–πšŽ.

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

specialisation: 𝚟𝚎𝚌_𝚎𝚚_πšπšžπš™πš•πšŽΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πš’πš—πšπšŽπšπšŽπš› in second argument).

Keywords

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

constraint network structure: Berge-acyclic constraint network.

filtering: arc-consistency.

final graph structure: acyclic, bipartite, no loop.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŽπšŒπšπš˜πš›1.πšŸπšŠπš›=πšŸπšŽπšŒπšπš˜πš›2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™΄π™²πšƒπ™Ύπš1|

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

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

Figure 5.196.1. Initial and final graph of the πš•πšŽπš‘_πšŽπššπšžπšŠπš• constraint
ctrs/lex_equalActrs/lex_equalB
(a) (b)
Automaton

FigureΒ 5.196.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 signature variable πš‚ i as well as the following signature constraint: (πš…π™°πš1 i β‰ πš…π™°πš2 i β‡”πš‚ i =0) ∧ (πš…π™°πš1 i =πš…π™°πš2 i β‡”πš‚ i =1).

Figure 5.196.2. Automaton of the πš•πšŽπš‘_πšŽπššπšžπšŠπš• constraint
ctrs/lex_equal1
Figure 5.196.3. Hypergraph of the reformulation corresponding to the automaton of the πš•πšŽπš‘_πšŽπššπšžπšŠπš• constraint
ctrs/lex_equal2