5.154. equivalent

DESCRIPTIONLINKSAUTOMATON
Origin

Logic

Constraint

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

Synonym

𝚎𝚚.

Arguments
πš…π™°πšπšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš…π™°πšβ‰₯0
πš…π™°πšβ‰€1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=2
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›β‰₯0
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›β‰€1
Purpose

Let πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ be a collection of 0-1 variables πš…π™°πš 1 ,πš…π™°πš 2 . Enforce πš…π™°πš=(πš…π™°πš 1 β‡”πš…π™°πš 2 ).

Example
(1,0,0)
(0,0,1)
(0,1,0)
(1,1,1)
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • All occurrences of 0 in πš…π™°πš and in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be set to 1.

Arg. properties

Functional dependency: πš…π™°πš determined by πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Counting
Length (n)2345678
Solutions4000000

Number of solutions for πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πš: domains 0..n

ctrs/equivalent-1-tikz

ctrs/equivalent-2-tikz

Length (n)2
Total4
Parameter
value

02
12

Solution count for πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πš: domains 0..n

ctrs/equivalent-3-tikz

ctrs/equivalent-4-tikz

Systems

ifOnlyIf in Choco, rel in Gecode, eqbool in JaCoP, #<=> in SICStus.

See also

common keyword: πšŠπš—πš, πš’πš–πš™πš•πš’, πš—πšŠπš—πš, πš—πš˜πš›, πš˜πš›, πš‘πš˜πš›Β (Boolean constraint).

implies: πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŠπš•πšžπšŽ, 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŒπšπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŒπšπš›.

Keywords

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

constraint arguments: pure functional dependency.

constraint network structure: Berge-acyclic constraint network.

constraint type: Boolean constraint.

filtering: arc-consistency.

modelling: functional dependency.

Automaton

FigureΒ 5.154.1 depicts the automaton associated with the πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πš constraint. To the first argument πš…π™°πš of the πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πš constraint corresponds the first signature variable. To each variable πš…π™°πš i of the second argument πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ of the πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πš constraint corresponds the next signature variable. There is no signature constraint.

Figure 5.154.1. Automaton of the πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πš constraint
ctrs/equivalent-5-tikz
Figure 5.154.2. Hypergraph of the reformulation corresponding to the automaton of the πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πš constraint
ctrs/equivalent-6-tikz