Re: [boost] Re: Experiment in Automata syntax

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-06-28 07:29:11

On Thursday 28 June 2001 05:41, you wrote:
> --- In boost_at_y..., Vladimir Prus <ghost_at_c...> wrote:
> > Well, this example is cursors' trump card. And, maybe, one can
>
> create real
>
> > DFA from intersection cursor with 'ccopy' algorithm? That would be
>
> rather
>
> > elegant way of computing automata intersection.
>
> Sure :
>
> DFA_matrix<> A;
> ccopy(A, dfirstc(intersectionc(A)));
>
> intersectionc is a helper function building an
> intersection_cursor<DFA_matrix<> > and
> dfirstc is a helper function building a
> dfirst_cursor<stack_cursor<intersection_cursor<DFA_matrix<> > > >
> (yes, types are getting complex with adapters, hence the use
> of the helper functions). ccopy is a triming copy algorithm, i.e.
> it does not copy the "unuseful" paths (not leading to an accepting
> state). clone makes an exact copy:
>
> clone(A, dfirstc(intersectionc(A)));
>
> > The question is: if "default" transitions are used by delta1, should
>
> they be
>
> > listed in delta2? I think no. Would such difference make sense?
>
> It's a question I came across a couple of times. The sink state
> handler returned by the DFA::delta1 function is simply a way for
> the user to check if the transition is defined, they do not appear
> in DFA::delta2. I think the decision should left up to the cursor
> implementer allowing different behavior according to his needs.
>
> > Good. So I think interested persons can start giving comments.
>
> Here's my
>
> > attempt.
> >
> > 1. Interface.
> > Rather good already, but
> > 	i) Adding tag to transition may be reasonable. (Consider, e.g.
>
> example
>
> > 	 of creating Mealy machine that Douglas Gregor gives).
> > 	ii) I would prefer if all member names were fully spelled, ---
> > 	delete_transition instead del_trans, &c. (Just personal
>
> opinion, of cause).
>
>
> i) ASTL has been focused on automata exclusively. Right now, I am
> working to extend the container-cursor-algorithm to other finite-state
> machines (transducers, graphs and trees even if they're not really
> considered state machines) and for instance I use the transition tag
> for
> transducers to store the output symbol (it is used also to store the
> value of a graph edge). This kind of extensions
> shouldn't be integrated in the purely automaton part of the library
> but rather as add-on on which we could rely to implement other
> concepts.

I doubt that adding the 'tag' should be considered an extension (tags are 
also often called decorators or properties). It is simply an extra template 
parameter that has a default empty class - the use may specify an alternative 
class to use that may store more data with each transition, vertex, or 
automaton.

Interpreting the this extra data can be left up to the user, or one could go 
with the property map concept as used in the Boost Graph library so that 
common cases can be coded as algorithms within the library.

> ii) why not.
>
> > 2. Portability.
> > Should be increased.
>
> For sure. I haven't really tried to compile it with another compiler
> than g++. I have used a subset of ASTL with VC++, that's why some
> parts are #defined with WIN32 but I haven't test the whole package.
>
> > 3.  Algorithms.
> > Should be more of them.
>
> Of course. In fact, we have been focused on "real-world" efficient
> algorithms so far. I mean we developed that library to use it in
> linguistic products (commercial or not) which are really demanding
> applications. That is why for instance we have a really
> fast minimization algorithm for acyclic automata but nothing about
> minimizing a cyclic automaton with more general algorithm as
> Hopcroft's which are much less efficient (trying to keep the automata
> acyclic and deterministic is a way to ensure efficiency). Of course,
> any new algorithm is welcome.
>
> Regards
> Vincent Le Maout.

        Doug