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.