Programming challenge: wildcard exclusion in cartesian products

[Dinko Tenev]

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?

> 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.  For improved asymptotic complexity in this case,
you need to be able to at least reject in mid-sequence, and that calls
for a slightly different concept of a FSA -- is this what you meant?

Cheers,

Dinko