Combinatorial automata theory can be seen as studying reachability in transformation semigroups. An interesting way of generalising this setting is by lifting it up to reachability in finite semigroups of rational matrices. Here, besides finite automata theory, other areas come into play, for example weighted automata, algebraic number theory, and multilinear algebra. I will explain several nice questions (such as mortality and minimum rank) that transfer from transformation semigroups to finite matrix semigroups. I will also explain the lack of mathematical structure that is brought by certain PSPACE-complete transformation semigroup problems.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne