On Tue, Oct 23, 2001 at 09:39:54AM -0500, Greg Bacon wrote: > : So... (is anyone still with me?) I contend that if you give me a > : regex (any regex), I can write a sub which takes a string and returns > : whether or not the string matches the regex that you gave me, and > : which runs in polynomial time. > > That seems obvious. If you have the luxury of the fixed expression > membership problem, then you can construct a DFA before you're asked > to check strings for membership.
I fear that my original message was rather unclear - I was specifically intending to allow back referencing. When back referencing is allowed, you *can't* in general construct a DFA. Indeed, all DFA-recognisable languages are regular, and the language defined by /^([ab]*)\1$/ is not. However, for all the backreffing regexen that I can think of, there seems to be some way to check membership in polynomial time. Hence I'm wondering whether there's a membership algorithm (for regexes with back referencing) whose time complexity is polynomial in the length of the string -- though potentially superpolynomial in the length of the regex. Alternatively (and this was my original request) can anyone suggest a regex for which there *isn't* an obvious polynomial-time fixed expression membership algorithm? > TANSTAAFL, though. As you pointed out, constructing the DFA in the > worst case will take time exponential in the length of the regular > expression; the fixed expression membership problem only allows you to > paper over this. It has practical significance though, if you're checking several megabytes of text for a match. That's why I'm suggesting that the NP-completeness of uniform matching may not be the cause for despair that most seem to think. .robin. -- "It really depends on the architraves." --Harl
