In message <[EMAIL PROTECTED]>, Robin Houston writes:
: 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. Once you have the DFA (it's unique, remember), then you need only feed the string to the DFA to test for membership in polynomial time. 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. Greg
