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

[TeXitoi]

"Christian Schulte" <cschulte at kth.se> writes:

> Maybe there are better algorithms that combine DFA construction with
> minimization to deal with the DFAs but for most cases it works fine for
> Gecode...

OK

> Is your regexp related to a real example or did you want to torture Gecode
> ;-)

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.

> I never thought about operations on DFAs as I thought one would use regexps
> anyway. The only hard part is in fact intersection, the rest is very simple.
> What do you need them for?

Naive intersection is quite simple because we can easily generate a
DFA, and then, Gecode minimizes it.  But an effective implementation
may be difficult.

I use inverse (giving the alphabet) a lot because sometime it is
easier to write the regex of the forbidden pattern than the allowed
one.  As a simple example, I have this kind of forbidden pattern:
 0110 (on a subsequence of 4 variables) which is very simple to write
using the inverse:
  inverse(DFA(REG(0)+REG(1)+REG(1)+REG(0)), alphabet)
but much more difficult to write directly.

I have pattern rules of the type "this pattern or that pattern". Here,
the union is useful, especially when one pattern is easier to write
with an inverse (else I can do REG r = firstPattern | secondPattern).

I can do what I have explain earlier using concatenation and
intersection of DFA (here, "+" is the concatenation of DFA):
  - first month: intersection(DFA(myReg), DFA(any(nbDaysIn1Month,
       nbDaysIn1Month))) + DFA(*any)
  - second month: DFA(any(nbDaysIn1Month,nbDaysIn1Month)) + 
        intersection(DFA(myReg,DFA(any(nbDaysIn1Month,nbDaysIn1Month)))) +
        DFA(*any)
  - ...

But maybe you have a better solution for the special problem I have
now: I have at least n_i "1" on each month_i, exactly m_j "1" on each
semester_j, and minimum one "1" on a slidding horizon of 7, and a
minimum of two "1" on a slidding horizon of 11.  The problem I have is
when there is a lot of possibilities for the first semester, but none
for the second (because of the 4 constraints, not because directly of
one of them), but the propagation do not detect the infeasibility of
the second semester. Of course, I cannot solve each semester
separatedly because there is pattern constraint that overlap.  For the
moment, I have a variable that "count" the "1" on each month, I use
rel to constraint these variables according to my data for the month
and the semester constraints, and I use sequence (in reality a count
for each interval of length 11, and an extensional for 1 on 7, which
is much faster than sequence) for the slidding constraints.  I also
have extensional version of these constraints.  The idea was to
combine the DFA to detect directly the infeasability.

I hope I am understandable.  Thanks for your attention.

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