Re: Automata Library

From: Vladimir Prus (ghost_at_[hidden])
Date: 2001-06-01 05:18:33

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.

-- 
Regards,
Vladimir