October 16, 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.