Weighted Register Automata

Abstract: Register automata are an extension of automata that deal with data, possibly from an infinite domain. Many results from classical automata theory generalise, as witnessed by the fact that many decision procedures still work on deterministic register automata. However, the nondeterministic register automata are strictly more expression and some properties are now undecidable.

Motivated by a recent result that the subclass of unambiguous register automata has decidable equivalence, we investigate weighted register automata. These generalise unambiguous (but not all nondeterministic) register automata. We show that equivalence is also decidable in this bigger class. This improves the previous results in three other ways: (a) we allow for more data domains; (b) the complexity is exponentially better; and (c) we allow automata with guessing.

Our crucial contribution is the development of the mathematical theory of so-called orbit-finitely spanned vector spaces, on which our decision procedure is based. In the talk I will mostly talk about these structures. This is joint work with Mikołaj Bojańczyk and Bartek Klin.

Bio: Joshua Moerman is Assistant Professor at the Open University. Previously he was a post doctoral researcher at the RWTH Aachen in the MOVES group. Before that, he was a PhD student at the Radboud University in Nijmegen at the Software Science department.