Re: [boost] Re: Automata Library

From: Revuz dominique (dr_at_[hidden])
Date: 2001-06-01 10:38:23

Vladimir Prus a écrit :

> ASTL's interface is nice. I have already thought that it is close to the best
> interface for automaton.

Thanks We have been working on this for 3 years.
The realy nice part is the Cursors:
    A mixture of iterator and visitor patterns. Have a look it is not in the
include dir but in astl/cursors/.
We are working on a Transductor library.

> >The code is optimal on several questions.
> Explain, please. Do you mean performance?

The objectives of our library was to build very efficients data structures to
implement automata:
Matrix<container>, Adjacency<container>, evolutive<Edge_Mover_Functor> etc.
The algorithms interface choices where made with this idea in mind :
    the interface could use any of those automata containers in any way.
    But has "ghost" says further down in this message : a given data structure
is good for a given task and bad for another.
    So we worked on a copy algorithm that would permit to pass from one form to
an other this the ccopy(cursor,dfa) ( triming copy) the dfa parameter is ther e
to choose the type of dfa. There is allso a clone() algorithm (perfect copy) .

> Last time I looked, it  had very
> straight-forward implementation of NFA->DFA convertion, which is unlikely to
> be fast. Was any improvements made?

I don't understand what you mean by straight-forward could you give me a pointer
on a paper on a good implementation.
The cursors can help ?! with a lazy_cursor<cursor> construct that builds the
DFA while parsing text with the NFA. This is very efficent for regexp and
pattern mattching technics in general, where the NFA is small and the DFA huge.

>
> 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?

No i didn't think about that ! Nor Vincent ;-)
The BGL is very vertex oriented and we are very edge oriented.

>
>
> 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.

An graph adapter for dfa could be writen of course.

>
>
> 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 don't think wanting a implementation that is good for both task is  a good
objective.
It is a better idea to propose a general interface for data structures capable
of storing
automata or transducers or graphs in general, and then write algorithms that use
this
common interface, then the final user can choose the rigth implementation of the

algorithm and the data structure in is own uniq case.
(i have allways surprises on what is the best mixture of algorithme and data
structure
 for a given case ;-).

Remark: The best part of our  algorithms are for acyclic automata that are very
usefull in practice,
but not the general case.

--
Dominique Revuz, Maitre de conference a Marne la Vallee
Bureau 4086 Copernic - 5, boulevard Descartes  Champs sur Marne
77454 Marne la Vallée CEDEX 2    FRANCE   Tel : [phone]
Fax: [phone] http://www-igm.univ-mlv.fr/~dr/