Hybrid set-vector automata from a category-theoretic perspective
The main purpose of this talk is to introduce a new automata
model, hybrid set-vector automata, that naturally embed deterministic
finite state automata and finite automata weighted over a field.
We take a category-theoretic approach, which provides a neat
understanding of minimisation. It is well known that category theory
offers a unifying view of some automata theory results. For example,
minimisation of deterministic automata (over finite words) and
Schützenberger's automata weighted over fields, arise from the same
categorical reasons.
In the first part of the talk, I will discuss about how to model and
minimise automata in categories. Traditionally, automata are seen
either as algebras for a functor plus a final map, possibly in a
monoidal category, or as coalgebras for a functor plus an initial
map. We propose yet another view of automata as functors from an input
category to an output category.
The new hybrid set-vector automata can be modelled by taking the
output category to be a free-colimit completion of the category of
finite-dimensional vector spaces under a certain class of colimits.
This is joint work with Thomas Colocombet.