Skip to main content

Automata in Glued Vector Spaces

Daniela Petrisan ( IRIF, Paris 7 )
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.

Share this: