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

Vars

Collection of (domain) variables or integers, or a collection of a collection of (domain) variables or integers.

RegExp

A regular expression

Description

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})

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