Re: Experiment in Automata syntax

From: vincent.lemaout_at_[hidden]
Date: 2001-06-28 04:41:17

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

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.