Dirk Thierbach wrote:
Dinko Tenev [EMAIL PROTECTED] wrote:
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
[EMAIL PROTECTED] wrote:
Call a wc 'free' if it satisfies the propery that every letter 'a' in
it appears only in the form '*a*', and 'anchored' otherwise. What if
all wc's are free? How does this affect the DFA? Does it minimize
nontrivially? Keep in mind I'm new to DFA theory.
There would
Dirk Thierbach wrote:
[A lot of stuff]
Now clearer?
- Dirk
Actually, it's getting all the messier, and we seem to be running
around in circles. I've already lost track of the point you're trying
to make, and it seems that you're missing most of my points.
Let's leave it there, and take a
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.
Dirk Thierbach wrote:
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
funkyj wrote:
How about the other iterator characteristics?
when there is a huge solution space can I ask the prolog version to
give me the first 1000 solutions?
Geoffrey's post above offers one way to do this from within a REPL.
Within a program, as soon as you accept a solution, you're
OK, here's a case that will make your program run in exponential time:
S = { a, b }, W = { *a*b, *b*a } -- on my machine, it starts getting
ugly as soon as n is 15 or so. Note that S^n - W = { a^n, b^n }.
In general, whenever all the patterns in the set match against the last
position, your
[EMAIL PROTECTED] wrote:
After the basic fact of generating the exclusion - a considerable
achievement - the program should be interactive. What if the target set
has thousands or millions of elements? There should be a loop-like way
('do' in Haskell, for example) to peel off the elements
Dinko Tenev wrote:
Speculation: the time for
building-up a smart structure to speed-up enumeration, together with
the time for enumerating the set using that structure, should sum up to
roughly Theta( n*|S^n| ), even with a really smart algorithm.
OK, maybe not.
This might be the worst case
Doug Quale wrote:
funkyj [EMAIL PROTECTED] writes:
One advantage of a generator over filtering the full product is that I,
as the user of the generator, am not obligated to iterate over the
entire solution space.
Are there other _practical_ advantages of generators over mapping
[EMAIL PROTECTED] wrote:
It would seem that your program is just filtering the full cartesian
product, right? The solution I'm looking for generates the elements
one-by-one so that it could be used in a loop.
OK, having read some of the comments so far, I have the feeling that I
may be missing
Roedy Green wrote:
On 15 Mar 2006 22:20:52 -0800, Xah Lee [EMAIL PROTECTED] wrote,
quoted or indirectly quoted someone who said :
e. For example, the in-fix
notation =E2=80=9C(3+(2*5))7=E2=80=9D is written as =E2=80=9C3 2 5 * + 7 =
=E2=80=9D, where the
Not that Mr. Lee has ever shown much
Heh, here's a Prolog version:
==
gen( _, 0, [] ) :- !.
gen( S, N, [H | T] ) :- member( H, S ), M is N - 1, gen( S, M, T ).
==
Yep, that's it :)))
Here's how to test it:
[EMAIL PROTECTED] wrote:
It would seem that your program is just filtering the full cartesian
product, right? The solution I'm looking for generates the elements
one-by-one so that it could be used in a loop.
Oops...missed that part.
It took me a while to study the exchange on this topic more
14 matches
Mail list logo
