Re: additional regular expression operators

On Apr 1, 3:07 am, Ralph Boland <rpbol...@gmail.com> wrote:
> I have never found a useful example of set intersection though.
> I have found so far only one paper on implementing these operators
> and it is complex.


While this is quite a special case, you might find it interesting. In
constraint programming regular languages can be used to specify
constraints. Given that more than one regular constraint can be and
typically is used at the same time over the same set of variables,
intersection of two regular languages can be used to strengthen
constraint propagation. It is not widely used, though, since the
intersection operation is quite often quadratic which makes the gain
in pruning power quite expensive.


When I implemented the intersection operation, it was quite simple,
although as said it was also inherently inefficient. The basic idea
(IIRC) was to take the product of the two automatas state-spaces which
allows the concurrent check of both languages.


Cheers,
MZL

Return to the comp.compilers page.
Search the comp.compilers archives again.