5.30. and

DESCRIPTIONLINKSAUTOMATON
Origin

Logic

Constraint

πšŠπš—πš(πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonym

πš›πšŽπš•.

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

Let πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ be a collection of 0-1 variables πš…π™°πš 1 ,πš…π™°πš 2 ,β‹―,πš…π™°πš n (nβ‰₯2). Enforce πš…π™°πš=πš…π™°πš 1 βˆ§πš…π™°πš 2 βˆ§β‹―βˆ§πš…π™°πš n .

Example
(0,0,0)
(0,0,1)
(0,1,0)
(1,1,1)
(0,1,0,1)
Symmetry

Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

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

  • Extensible wrt. πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ when πš…π™°πš=0.

  • Aggregate: πš…π™°πš(∧), πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚(πšžπš—πš’πš˜πš—).

Counting
Length (n)2345678
Solutions48163264128256

Number of solutions for πšŠπš—πš: domains 0..n

ctrs/and-1-tikz

ctrs/and-2-tikz

Length (n)2345678
Total48163264128256
Parameter
value

037153163127255
11111111

Solution count for πšŠπš—πš: domains 0..n

ctrs/and-3-tikz

ctrs/and-4-tikz

Systems

reifiedAnd in Choco, rel in Gecode, andbool 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.

Cond. implications

β€’ πšŠπš—πš(πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Β Β Β  withΒ  |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2

Β Β implies πšœπš˜πš–πšŽ_πšŽπššπšžπšŠπš•(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚).

β€’ πšŠπš—πš(πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Β Β Β  withΒ  πš…π™°πš=0

Β Β implies πš—πšŠπš—πš(πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Β Β Β  whenΒ  πš…π™°πš=1.

β€’ πšŠπš—πš(πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Β Β Β  withΒ  πš…π™°πš=1

Β Β implies πš—πšŠπš—πš(πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Β Β Β  whenΒ  πš…π™°πš=0.

Automaton

FigureΒ 5.30.1 depicts a first deterministic automaton without counter 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.30.1. Counter free automaton of the πšŠπš—πš(πš…π™°πš,βŒ©πš…π™°πš 1 ,πš…π™°πš 2 ,β‹―,πš…π™°πš n βŒͺ) constraint (the transition iβ†’ πš…π™°πš i =0k represents the fact that at least one variable πš…π™°πš i should be set to 0 when πš…π™°πš=0, while the transition jβ†’ πš…π™°πš i =1j represents the fact that all πš…π™°πš i should be set to 1 when πš…π™°πš=1)
ctrs/and-5-tikz
Figure 5.30.2. Hypergraph of the reformulation corresponding to the automaton of the πšŠπš—πš constraint
ctrs/and-6-tikz

FigureΒ 5.30.3 depicts a second deterministic automaton with one counter associated with the πšŠπš—πš constraint, where the argument πš…π™°πš is unified to the final value of the counter.

Figure 5.30.3. Automaton (with one counter) of the πšŠπš—πš constraint
ctrs/and-7-tikz
Figure 5.30.4. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the πšŠπš—πš constraint (since all states of the automaton are accepting there is no restriction on the last variable Q n )
ctrs/and-8-tikz