[gecode-users] Problems with some REG and some suggestions

[Guido Tack]

On 28 Sep 2011, at 16:09, TeXitoi wrote:

> Guido Tack <tack at gecode.org> writes:
> 
>> On 27 Sep 2011, at 11:43, TeXitoi wrote:
>>> I work on about 400 integer variables (about 15 months), and I have
>>> regex that are applied on different intervals (year, semester, month,
>>> week...).  To improve the performances, I would like to combine some
>>> of the constraints on a unique DFA. So, the idea I had was generating
>>> a regex that affect only a period but that have the length of my
>>> problem:
>>> - first month : myReg + any(nbDaysIn14Month,nbDaysIn14Month)
>>> - second month : any(nbDaysIn1Month,nbDaysIn1Month) + myReg +
>>>       any(nbDaysIn13Month,nbDaysIn13Month)
>>> - ...
>>> - first semester : ...
>>> - ...
>>> and then I compute the intersection of the DFA.
>> 
>> One thing I noticed (but which may be just because you simplified
>> the problem for presentation) is that you could build expressions
>> for a whole year without any wildcards, e.g.
>> 
>> year = myReg(15,15)
> 
> Interesting idea.  But it does not work just like that: imagine you
> have a 2 week problem and that you want 2 consecutive "1" each week.
> 
>  REG myReg = *any + one(2,2) + *any;
> 
> if we do what you said (myReg(2,2)), the string
> 
>  1111000 0000000
> 
> will match.  We have 2 consecutive "1" on the first week but 0 on the
> second.  To make this work, you need to do the intersection of
> DFA(myReg) with DFA(any(7,7)).  I cannot see how to do it without
> concatenation of DFA.

Right, of course.  I somehow assumed myReg was one month long, but of course you use the any(...) to make it exactly one month long.

> Then, this is not so simple, some patterns must use some characters
> before and after the period to work correctly, and so the regexen
> overlap, and you cannot use this idea.

Yes, I had already expected that overlap could be a problem.

Cheers,
Guido

-- 
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/