Dinko Tenev <[EMAIL PROTECTED]> wrote: > Dirk Thierbach wrote: >> If more time during preprocessing is allowed, another idea is to >> treat the wildcard expressions as regular expressions, convert >> each into a finite state machine, construct the "intersection" of >> all these state machines, minimize it and then swap final and non-final >> states.
> Given the requirements, did you mean taking the *union* and swapping > states? Or maybe swapping states first, and then taking the > intersection? Whatever the requirements were. Take your pick. :-) >> Then you can use the resulting automaton to efficiently >> enumerate S^n - W. In the above case, the resulting FSM would have just >> three states. > I don't see immediately how exactly this is going to work. Unless I'm > very much mistaken, a FSA in the classical sense will accept or reject > only after the whole sequence has been consumed, and this spells > exponential times. Exponential in respect to what? You just recursively walk the automaton for every word of length n, so at most you'll have to check every word in S^n once. Hence, the complexity is not worse than the "generate and test" approach (it's in fact better, since testing is trivial). However, if the result set is simple (as in the example), then the result FSM will have states that won't have transitions for every letters, so I guess the average case will be a lot better. > For improved asymptotic complexity in this case, > you need to be able to at least reject in mid-sequence, One can do that if there is no valid transition out of some state. I guess one could even optimize on that: In the minimal automaton, every state has some transition sequence that will end up in a final state. Annotate each state with the minimum number of steps for such a sequence. While walking the automaton, keep the maximum number of letters to produce in a variable. If this number is small then the number in the annotation, stop and backtrace. This should guarantee that only those states are visited that really produce some output. - Dirk -- http://mail.python.org/mailman/listinfo/python-list