# Re: What is regular about regular expressions nowadays?

**From:** Michael N. Christoff (*mchristoff_at_sympatico.caREMOVETHIS*)

**Date:** 01/16/04

**Next message:**Kent Paul Dolan: "Re: What is regular about regular expressions nowadays?"**Previous message:**Kent Paul Dolan: "Re: A Class of Non-Halting TMs"**In reply to:**Kent Paul Dolan: "Re: What is regular about regular expressions nowadays?"**Next in thread:**Kent Paul Dolan: "Re: What is regular about regular expressions nowadays?"**Reply:**Kent Paul Dolan: "Re: What is regular about regular expressions nowadays?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

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

"Kent Paul Dolan" <xanthian@well.com> wrote in message

news:acaa990a77438a36c2b80392f901353a.48257@mygate.mailgate.org...

*> "Sriram" <sriram@malhar.net> 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

**Next message:**Kent Paul Dolan: "Re: What is regular about regular expressions nowadays?"**Previous message:**Kent Paul Dolan: "Re: A Class of Non-Halting TMs"**In reply to:**Kent Paul Dolan: "Re: What is regular about regular expressions nowadays?"**Next in thread:**Kent Paul Dolan: "Re: What is regular about regular expressions nowadays?"**Reply:**Kent Paul Dolan: "Re: What is regular about regular expressions nowadays?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]