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
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.