5.188. increasing_nvalue_chain
DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
For each consecutive pair of items of the collection at least one of the following conditions hold:
,
.
In addition, is equal to number of pairs of variables plus one, which verify at least one of the following conditions:
,
.
Note that is not referenced at all in the previous definition (i.e.,Β its value does not influence at all the values assigned to the other variables).
- Example
-
The constraint holds since:
The condition holds for every pair of adjacent items of the collection:
For the pair we have .
For the pair we have .
For the pair we have .
For the pair we have .
For the pair we have .
For the pair we have .
For the pair we have .
For the pair we have .
is equal to number of pairs of variables plus one which verify at least . Beside the plus one, the following five pairs contribute for 1 in :
For the pair we have .
For the pair we have .
For the pair we have .
For the pair we have .
For the pair we have .
- Typical
- See also
related: , , .
- Keywords
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.188.1 respectively show the initial and final graph associated with the second graph constraint of the Example slot. Since we use the graph property the arcs of the final graph are stressed in bold.
Figure 5.188.1. Initial and final graph of the constraint
(a) (b)
- Automaton
-
Without loss of generality, assume that the collection contains at least one variable (i.e.,Β ). Let , , , and respectively denote the minimum and maximum possible value of variable , the number of items of the collection , the smallest value that can be assigned to , and the largest value that can be assigned to . Let denote the total number of potential values. Clearly, the maximum value of cannot exceed the quantity . The states of the automaton that only accepts solutions of the constraint can be defined in the following way:
We have an initial state labelled by .
We have states labelled by .
Terminal states depend on the possible values of variable and correspond to those states such that is a possible value for variable . Note that we assume no further restriction on the domain of (otherwise the set of accepting states needs to be reduced in order to reflect the current set of possible values of ).
Transitions of the automaton are labelled by a pair of values and correspond to a condition of the form , . Characters and respectively represent all values in and all values in . Four classes of transitions are respectively defined in the following way:
There is a transition, labelled by the pair , from the initial state to the state . We use the character since is not use at all in the definition of the constraint.
There is a loop, labelled by the pair for every state .
there is a transition labelled by the pair from to .
there is a transition labelled by the pair from to .
Figure 5.188.2. Automaton of the constraint under the hypothesis that all variables are assigned a value in and that is equal to 2. The character on a transition corresponds to a 0 or to a 1 and the corresponds to a 6, 7 or 8.