Re: Experiment in Automata syntax

From: dg_at_[hidden]
Date: 2001-06-28 07:20:28

--- In boost_at_y..., vincent.lemaout_at_c... wrote:
> ...
> 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.

When you speak of "the output symbol," do you mean that sequences of
output symbols won't be allowed on edges? Of course, the
determinization and minimization algorithms for transducers will
introduce such sequences.

I'd be interested to know how the the interface for applying a
transducer would be. In case the transducer is functional, you might
consider something like STL transform(), which writes it's outputs to
an output iterator. The problem is, however, you don't know that you
should be outputting anything until you know that the input leads you
to a final state. So perhaps applying a transducer to an input string
should return an automaton representing all transductions. Is this
what you had in mind?

If you're extending ASTL for transducers, how about weighted
transducers as well? Actually, I've seen the work by Arnaud Adant,
doing exactly this. But it wasn't exactly clear to me whether that was 
just a student project or if that was work that would be incorporated
into ASTL.

Now, since I'm pushing my luck anyway, how about allowing weights in 
different user-specified semirings?

-- Dale Gerdemann