5.152. in

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Domain definition.

Constraint

πš’πš—(πš…π™°πš,πš…π™°π™»πš„π™΄πš‚)

Synonyms

πšπš˜πš–, πš’πš—_𝚜𝚎𝚝.

Arguments
πš…π™°πšπšπšŸπšŠπš›
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
Restrictions
|πš…π™°π™»πš„π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
Purpose

Enforce the domain variable πš…π™°πš to take a value within the values described by the πš…π™°π™»πš„π™΄πš‚ collection.

Example
(3,1,3)

The πš’πš— constraint holds since its first argument πš…π™°πš=3 occurs within the collection of values πš…π™°π™»πš„π™΄πš‚=〈1,3βŒͺ.

Typical
|πš…π™°π™»πš„π™΄πš‚|>1
Symmetries
  • Items of πš…π™°π™»πš„π™΄πš‚ are permutable.

  • πš…π™°πš can be set to any value of πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•.

  • One and the same constant can be added to πš…π™°πš as well as to the πšŸπšŠπš• attribute of all items of πš…π™°π™»πš„π™΄πš‚.

Remark

Entailment occurs immediately after posting this constraint.

The πš’πš— constraint is called πšπš˜πš– inΒ Gecode (http://www.gecode.org/).

Systems

member in Choco, in in JaCoP, in in SICStus, in_set in SICStus.

Used in

πšŠπš–πš˜πš—πš, πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πšŠπšπš–πš˜πšœπš_πš™πšŠπš›πšπš’πšπš’πš˜πš—, πšπš›πš˜πšžπš™, πšπš›πš˜πšžπš™_πšœπš”πš’πš™_πš’πšœπš˜πš•πšŠπšπšŽπš_πš’πšπšŽπš–, πš’πš—_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—, πš˜πš™πšŽπš—_πšŠπš–πš˜πš—πš.

See also

common keyword: πšπš˜πš–πšŠπš’πš—Β (domain definition), πš’πš—_πš’πš—πšπšŽπš›πšŸπšŠπš•, πš’πš—_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—, πš’πš—_𝚜𝚎𝚝 (value constraint).

implied by: πš–πšŠπš‘πš’πš–πšžπš–, πš–πš’πš—πš’πš–πšžπš–.

negation: πš—πš˜πš_πš’πš—.

Keywords

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

constraint arguments: unary constraint.

constraint network structure: centered cyclic(1) constraint network(1).

constraint type: value constraint.

filtering: arc-consistency.

modelling: included, domain definition.

Derived Collection
πšŒπš˜πš•(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),[πš’πšπšŽπš–(πšŸπšŠπš›-πš…π™°πš)])
Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ πš…π™°π™»πš„π™΄πš‚

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš•
Graph property(ies)
𝐍𝐀𝐑𝐂=1

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.152.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.

Figure 5.152.1. Initial and final graph of the πš’πš— constraint
ctrs/inActrs/inB
(a) (b)
Signature

Since all the πšŸπšŠπš• attributes of the πš…π™°π™»πš„π™΄πš‚ collection are distinct and because of the arc constraint πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš• the final graph contains at most one arc. Therefore we can rewrite 𝐍𝐀𝐑𝐂=1 to 𝐍𝐀𝐑𝐂β‰₯1 and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.

Automaton

FigureΒ 5.152.2 depicts the automaton associated with the πš’πš— constraint. Let πš…π™°π™» i be the πšŸπšŠπš• attribute of the i th item of the πš…π™°π™»πš„π™΄πš‚ collection. To each pair (πš…π™°πš,πš…π™°π™» i ) corresponds a 0-1 signature variable πš‚ i as well as the following signature constraint: πš…π™°πš=πš…π™°π™» i β‡”πš‚ i .

Figure 5.152.2. Automaton of the πš’πš— constraint
ctrs/in1
Figure 5.152.3. Hypergraph of the reformulation corresponding to the automaton of the πš’πš— constraint
ctrs/in2