Global Constraint Catalog: Cnor

5.281. nor

DESCRIPTION

LINKS

AUTOMATON

Origin

Logic

Constraint

$𝚗𝚘𝚛 (𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Synonym

$𝚌𝚕𝚊𝚞𝚜𝚎$ .

Arguments

$𝚅𝙰𝚁$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝚅𝙰𝚁 \geq 0

𝚅𝙰𝚁 \leq 1

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | \geq 2

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛 \geq 0

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛 \leq 1

Purpose

Let $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ be a collection of 0-1 variables ${𝚅𝙰𝚁}_{1}, {𝚅𝙰𝚁}_{2}, \dots, {𝚅𝙰𝚁}_{n}$ $(n \geq 2)$ . Enforce $𝚅𝙰𝚁 = \neg ({𝚅𝙰𝚁}_{1} \lor {𝚅𝙰𝚁}_{2} \lor \dots \lor {𝚅𝙰𝚁}_{n})$ .

Example

(1, 〈0, 0〉)

(0, 〈0, 1〉)

(0, 〈1, 0〉)

(0, 〈1, 1〉)

(0, 〈1, 0, 1〉)

Symmetry

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.

Arg. properties

Functional dependency: $𝚅𝙰𝚁$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚅𝙰𝚁 = 1$ .
Extensible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚅𝙰𝚁 = 0$ .
Aggregate: $𝚅𝙰𝚁 (\land)$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 (𝚞𝚗𝚒𝚘𝚗)$ .

Counting

Length ( $n$ )	2	3	4	5	6	7	8
Solutions	4	8	16	32	64	128	256

Number of solutions for $𝚗𝚘𝚛$ : domains $0 . . n$

ctrs/nor-1-tikz

ctrs/nor-2-tikz

Length (

n

)

Total

128

256

Parameter

value

127

255

Solution count for $𝚗𝚘𝚛$ : domains $0 . . n$

ctrs/nor-3-tikz

ctrs/nor-4-tikz

Systems

reifiedXnor in Choco, clause in Gecode, #\/ in SICStus.

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 $𝚜𝚘𝚖𝚎_𝚎𝚚𝚞𝚊𝚕$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ .

Automaton: Figure 5.281.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.281.1. Automaton of the $𝚗𝚘𝚛$ constraint

Figure 5.281.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚗𝚘𝚛$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.281. nor

Figure 5.281.1. Automaton of the $𝚗𝚘𝚛$ constraint

Figure 5.281.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚗𝚘𝚛$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.281. nor

Figure 5.281.1. Automaton of the 𝚗𝚘𝚛 constraint

Figure 5.281.2. Hypergraph of the reformulation corresponding to the automaton of the 𝚗𝚘𝚛 constraint

Figure 5.281.1. Automaton of the $𝚗𝚘𝚛$ constraint

Figure 5.281.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚗𝚘𝚛$ constraint