Linear Recurrence Sequences, Weighted Automata and their Ambiguity

17^th March 2023, 13:00 Ashton Lecture Theatre
Dr. David Purser
Department of Computer Science, University of Liverpool

Abstract

The classical Fibonacci sequence takes the sum of the previous two terms as its value at each step. In general, sequences that take a linear combination of the previous terms are linear recurrence sequences. Such sequences model the evolution of program variables in linear loops, that is, when each program variable is updated using a linear transformation. More generally we can consider weighted automata, which can apply different linear transformations at each step. The talk will give a gentle introduction to these models and look at some important problems in the field. One important property for the analysis of weighted automata is ambiguity: the number of accepting paths through the automaton for every word. We consider the unambiguisation problem, which asks whether there is an equivalent weighted automaton with at most a single run for every word.

Biography

I am a lecturer of computer science at the University of Liverpool since January 2023. My research interests are in weighted automata, vector addition systems and infinite state systems. Previously I was a postdoctoral researcher at The University of Warsaw, Poland and at The Max Planck Institute for Software Systems in Saarbrücken, Germany. I completed my PhD in computer science at the University of Warwick.