Re: What is regular about regular expressions nowadays?

From: Michael N. Christoff (mchristoff_at_sympatico.caREMOVETHIS)
Date: 01/16/04

Date: Fri, 16 Jan 2004 00:34:04 -0500

"Kent Paul Dolan" <> wrote in message
> "Sriram" <> wrote:
> > Befuddled minds want to know.
> It's been a couple decades, but check the disclaimers
> for those parsers. I seem to recall the word "exponential"
> sneaking in somewhere, might have been space, might have been
> time, for worst case behavior, but as I said, it's been a
> couple of decades.

There is the concept of "regular expressions with exponentiation". ie: If
R is a regular expression, and k in N, then R^k = R concatenated with itself
k times. I have only seen exponentiation used in the canonical
EXSPACE-complete language EQ_REX-E = {<Q,R> | Q and R are equivalent regular
expressions with exponentiation}. So I would guess what you saw may not
have had anything to do with exponential time algorithms.

> We tend to use lots of tools whose worst case behavior would
> wreck our lives, because that case is too rare to encounter in
> one tool lifetime without deliberately constructing it.

I would guess that this is not true, since the algorithm writer has no idea
what possible regular expressions may be used. ie: it is rare that
language/api designers would use an exponential time algorithm and not at
least mention this in the docs. Especially for such widely used apis as
found in Java, Perl and .NET since people routinely use such languages for
mission-critical apps where a computation that takes days (or more) to
complete can mean the loss of millions of dollars.

And although I'm sure you know this - even if the alg is exponential only in
what may seem like contrived cases - the alg is still defined as
exponential. Besides, what may seem like a contrived case to you or I, may
be an everyday occurence in certain applications.

What you mentioned, however, is common place in randomized algorithms (ie:
randomized quicksort), but in the "one-in-a-million" chance the alg hits its
worst case, its worst case is still polynomial (at least in the randomized
algs I've dealt with).

Same thing with probabalistic algs - but in this case instead of being
exponential in the worst case, the alg may actually give an incorrect answer
(ie: accepts or rejects incorrectly - see the complexity class BPP for a
simple example).

l8r, Mike N. Christoff