[ library(gfd) | Reference Manual | Alphabetic Index ]

<ConsistencyModule:> regular(+Vars, ++RegExp)

Constrain Vars' solutions to conform to that defined in the regular expression RegExp.
Vars
Collection of (domain) variables or integers, or a collection of a collection of (domain) variables or integers.
RegExp
A regular expression

Description

regular is a user defined constraint, i.e. the solutions for the each posted constraint is defined within the constraint. For regular, the regular expression in RegExp defines the sequence of values that the variables for the constraint can take.

Vars represents the variables that are to be satisfied for this constraint. It can be one collection of variables (or integers), or a collection of a collections of variables (or integers), if the constraint is to be satisfied by more than one collection of variables. Each collection can be of different size, i.e. have different number of variables. Posting the constraint with multiple collections of variables is logically equivalent to posting individual constraint with the same RegExp for each collection, but should be more efficient as the same RegExp is shared by all the collections.

RegExp is a regular expression that defines the allowable sequence of values that can be taken by the variables. The syntax is as follows:

N
N is the integer value taken by a variable.
+(RegExp)
RegExpr is repeated 1 or more times
*(RegExp)
RegExpr is repeated 0 or more times
RegExp1 + RegExp2
RegExp1 is followed by RegExp2
(RegExp1 | RegExp2)
RegExp1 and RegExp2 are alternatives
(RegExp, {N,M})
RegExp is repeated at least N times, and at most M times. (N, M are non-negative integers)
(RegExp, {N})
RegExp is repeated at least N times (N is a non-negative integer)
ValueCollection
ValueCollection is a collection of integer values. Each value is a value that the variable is allowed to take in this position.

Regular expression uses existing standard ECLiPSe operators and functors, so the syntax is slightly different from the standard syntax, and it maps to the regular expression used by Gecode for this constraint. For example, the following

RegExp = +(0) + (1, {3,3})
specifies a sequence of 1 or more 0s followed by 3 1s. e.g. [0,0,1,1,1].

The possible values for a sequence of variables can also be specified by extensional/4, but using regular expression is probably more convenient, both constraints map to same underlying implementation. For a sequence of fixed length, the solutions can also be specified using the table/2 constraint.

ConsistencyModule is the optional module specification to give the consistency level for the propagation for this constraint: gfd_gac for generalised arc consistency (domain consistency).

This constraint is implemented in Gecode as the extensional() constraint with the variant that takes a DFA (Deterministic Finite-state Automaton) as an argument, with the regular expression converted to a DFA.

Examples

[eclipse 8]: regular([0,0,0,1,1,0,0], *(0) + *(1) + +(0)).  % succeed

[eclipse 9]:  L = [A,B,C,D,E], regular(L,  *(0) + *(1) + +(0)),
labeling(L), writeln(L), fail.
[0, 0, 0, 0, 0]
[0, 0, 0, 1, 0]
[0, 0, 1, 0, 0]
[0, 0, 1, 1, 0]
[0, 1, 0, 0, 0]
[0, 1, 1, 0, 0]
[0, 1, 1, 1, 0]
[1, 0, 0, 0, 0]
[1, 1, 0, 0, 0]
[1, 1, 1, 0, 0]
[1, 1, 1, 1, 0]

No (0.00s cpu)

[eclipse 10]: regular([A,B,C,D,E,F], ([1, 3, 5], {1, 2}) + *(4))

A = A{[1, 3, 5]}
B = B{[1, 3 .. 5]}
C = 4
D = 4
E = 4
F = 4

See Also

extensional / 4, table / 2