Skip to main content

Weighted Register Automata

Seminar by Joshua Moerman (Open University)

  • Date 24 Mar 2021
  • Time 3.00opm-4.00pm
  • Category Seminar

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. 

moerman-pic.jpg

Related topics

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones

Heading to university is exciting. Finding the right place to live will get you off to a good start

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help

Discover more about our 21 departments and schools

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’

They say the two most important days of your life are the day you were born, and the day you find out why

Discover world-class research at Royal Holloway

Discover more about who we are today, and our vision for the future

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today

We’ve played a role in thousands of careers, some of them particularly remarkable

Find about our decision-making processes and the people who lead and manage Royal Holloway today