16 octobre 2017

Daniela Petrisan (IRIF)

We introduce a new automata model, hybrid set-vector automata, designed to
accept weighted languages over a field in a more efficient way than Schützenberger’s weighted automata. The space of states for these automata is not a vector space, but rather a union of vector spaces « glued » together along subspaces. We call them hybrid automata,
since they naturally embed both deterministic finite state automata and finite automata
weighted over a field.  We prove that these automata can be minimized.  However, proving the existence of minimal automata “by hand” is rather complicated. Instead we adopt a more systematic approach and discuss the properties of the category of « glued » vector spaces that render minimization possible.

This is joint work with Thomas Colcombet. The talk can be either in English or French, depending on the audience’s preference.