Friday Lunch and Talk Series
Linear Recurrence Sequences, Weighted Automata and their Ambiguity
17th 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.
Maintained by Qiyi Tang