Linear Recurrence Sequences, Weighted Automata and their Ambiguity

17^th March 2023, 13:00 Ashton Lecture Theatre
David Purser

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.