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

[TeXitoi]

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.

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.

-- 
Guillaume Pinot                               http://www.texitoi.eu

« Il semble que la perfection soit atteinte non quand il n'y a plus
rien à ajouter, mais quand il n'y a plus rien à retrancher. »
                      -- Antoine de Saint-Exupéry, Terre des hommes

()  ASCII ribbon campaign      -- Against HTML e-mail
/\  http://www.asciiribbon.org -- Against proprietary attachments