
Boost : 
From: vincent.lemaout_at_[hidden]
Date: 20010628 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 containercursoralgorithm to other finitestate
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 addon 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 "realworld" 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk