Re: additional regular expression operators

MZL <zayenz@gmail.com>
Wed, 15 Apr 2009 07:57:04 -0700 (PDT)

          From comp.compilers

Related articles
additional regular expression operators rpboland@gmail.com (Ralph Boland) (2009-03-29)
Re: additional regular expression operators m.helvensteijn@gmail.com (2009-03-30)
Re: additional regular expression operators zaimoni@zaimoni.com (2009-03-30)
Re: additional regular expression operators haberg_20080406@math.su.se (Hans Aberg) (2009-03-30)
Re: additional regular expression operators torbenm@pc-003.diku.dk (2009-03-31)
Re: additional regular expression operators rpboland@gmail.com (Ralph Boland) (2009-03-31)
Re: additional regular expression operators torbenm@pc-003.diku.dk (2009-04-14)
Re: additional regular expression operators zayenz@gmail.com (MZL) (2009-04-15)
Re: additional regular expression operators anton@mips.complang.tuwien.ac.at (2009-04-16)
Re: additional regular expression operators gah@ugcs.caltech.edu (glen herrmannsfeldt) (2009-04-16)
Re: additional regular expression operators torbenm@pc-003.diku.dk (2009-04-17)
Re: additional regular expression operators mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2009-04-17)
RE: additional regular expression operators quinn_jackson2004@yahoo.ca (Quinn Tyler Jackson) (2009-04-21)
| List of all articles for this month |

From: MZL <zayenz@gmail.com>
Newsgroups: comp.compilers
Date: Wed, 15 Apr 2009 07:57:04 -0700 (PDT)
Organization: Compilers Central
References: 09-03-111 09-03-123 09-04-001
Keywords: lex

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



Post a followup to this message

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