Come on, keep cool! I just can't resist a good pun! =)

Just think of me as too ignorant as to fully understand your question... ;-)

> and if you have a FINITE SET of input strings, the cardinality of the sets that represent the results of the presented regexs may very well differ and thus be sortable. So your ivory tower arguments are mostly for the dustbin...

true, but you only limited the sets of input strings and not the sets of regexes or allowed regex commands.

IIRC Friedl (or perldocs?) describes in his book a regex with only two nested parens and quantifiers which would recursively backtrack for years!

Without a detailed description we have to answer the question in generality, and fast solutions are not really likely!