[Top][All Lists]

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

Re: [gnugo-devel] DFA suggestions

From: Tanguy URVOY
Subject: Re: [gnugo-devel] DFA suggestions
Date: Mon, 30 Sep 2002 10:13:35 +0200

Heikki Levanto wrote:
> On Mon, Sep 23, 2002 at 11:22:54AM +0100, Dave Denholm wrote:
> > Eg  Having matched string 'X..O.X', report a hit against pattern 42, then
> > advance -1 steps in the spiral and try the next node.
> I haven't studied the DFA thing at all, but I have been thinking that the
> pattern matching could possibly be more effective.
> For the first, the DFA follows always the same path. It ought to be possible
> to choose (at compile time) the most effective point to test, so as to
> eliminate the most patterns if the test fails. If these tests can also be
> off-board tests, we should be able to quickly skip patterns that can not be
> at a given point at all.
> Unfortunately I do not have the time to code this, nor enough experience in
> pattern matching to say if this is likely to give real-life benefits.
> Comments?

One of the most important features of DFAs is their
determinism: alway use the same path is necessary to preserve 
this determinism.
A good solution is to use one different DFA for each intersection 
and one path for each DFA but we may also decide to use partially
automaton to save memory.
There is a lot to do in pattern matching, 
when my phd will be written maybe...


Tanguy Urvoy

reply via email to

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