Re: [boost] Re: Automata Library

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-06-01 11:45:48

On Friday 01 June 2001 06:18 am, you wrote:
> dr_at_[hidden] wrote:
> >Hi folks,
> >been working with Vincent on the following library and maybe you want
> >to add it to your boost  list.
> >It really boost acyclic/DFA/NFA/Tranductor using software.
>
> ASTL's interface is nice. I have already thought that it is close to the
> best interface for automaton.
>
> >The code is optimal on several questions.
>
> Explain, please. Do you mean performance? Last time I looked, it  had very
> straight-forward implementation of NFA->DFA convertion, which is unlikely
> to be fast. Was any improvements made?
>
> Jeremy Siek wrote:
> >ASTL looks neat... to bad the BGL wasn't around when you starting working
> >on it. Have you thought at all about converting ASTL to use the BGL
> >interface?
>
> Douglas Gregor wrote:
> >Jeremy has a very good point. An automata library could benefit greatly
> > from the algorithms that already exist in the Graph library. We would be
> > foolish not to construct/adapt the automaton structures to the Graph
> > concept.
>
> I am very sceptical about this idea. After all, automaton should do one
> thing -- perform transition, and do it fast, whereas traversing  adjacent
> vertices may be slow or not supported. This is quite different from graph.
> Unless I'm shown an implementation doing both tasks equally well, I won't
> belive such can be written.

I'm not saying that we should use the Graph library's data structures, but 
that automata should all model the graph concepts from the Graph library, and 
thereby allow the algorithms from the graph library to be reused.

AFAIK the major different between NFA/DFA implementation and graph 
implementation is that in an NFA/DFA one needs fast lookup of edges based on 
some input symbol, whereas the input symbol for an edge in a "normal" graph 
would just be an edge decorator. This differences necessitates a separate 
implementation of NFAs/DFAs, but it does not change the fact that NFAs/DFAs 
are models of graphs. 

        Doug