[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
deterministic
automaton to save memory.
There is a lot to do in pattern matching,
when my phd will be written maybe...
Tanguy
--
-------------------------------------
Tanguy Urvoy http://www.turvoy.fr.st
-------------------------------------
Re: [gnugo-devel] Error in regression failure HTML view, Arend Bayer, 2002/09/22
Re: [gnugo-devel] Error in regression failure HTML view, Trevor Morris, 2002/09/23