Bi-Weekly Talk: Joshua Moerman: Weighted Register Automata

Wednesday, March 10, 2021, 10:30am

Location: Online session

Already at 10:00 we meet for a break: Let’s talk, exchange, chat and drink coffee or tea.

Speaker: Joshua Moerman

 

Abstract: 

We introduce the concept of weighted register automata, the common generalisation of weighted automata and register automata for infinite alphabets. By developing the underlying theory of vector spaces spanned by orbit-finite sets, we give a decision procedure for equivalence of these automata. As a special case, we can decide language equivalence for unambiguous register automata, which improves previous recent results in three ways: (a) we allow for order comparisons on atoms, and not just equality; (b) the complexity
is exponentially better; and (c) we allow automata with guessing. In this talk I will also discuss another special case, namely that of probabilistic register automata.

This is joint work with Mikołaj Bojańczyk and Bartek Klin.