[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [gnugo-devel] mkdfa.c

From: Tanguy URVOY
Subject: Re: [gnugo-devel] mkdfa.c
Date: Tue, 05 Nov 2002 10:17:44 +0100

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]