Re: [gnugo-devel] mkdfa.c

[Tanguy URVOY]

Dave Denholm wrote:
> 
> For what it's worth, here's the version of (what I called) mkdfa.c
> to generate a dfa that doesn't merge paths with different histories.
> 
> Looking back at it, it increases the number of states by far more than I
> had realised, and so is possibly not viable. Don't know if it is
> inherent because of the number of different possible routes, or
> if it is a bug in my implementation which fails to merge some
> possible branches.

Maybe I did not understand but a dfa that doesn't 
merge pathes with different prefix
is what I call a deterministic tree.

The good point with trees is the ability to insert
patterns at runtime.
The problem is the number of wildcards:
The number of states for a pattern with 
n wildcards is greater than 3^n

-- 
-------------------------------------
Tanguy Urvoy http://www.turvoy.fr.st
-------------------------------------