BCS-­FACS Evening Seminar Joint event with the London Mathematical Society

Date/Time: Wednesday 22 October 2014, 6.00pm
Refreshments will be available from 5.30pm.

Venue: London Mathematical Society, De Morgan House 57-­58 Russell Square, London WC1B 4HS

Cost to attend: Free of charge and open to everyone.

If you would like to attend, please register at computerscience@lms.ac.uk

Speaker: Professor Joel Ouaknine (University of Oxford)


Decision Problems for Linear Recurrence Sequences

Professor Joel OuaknineLinear recurrence sequences (LRS), such as the Fibonacci numbers, permeate vast areas of mathematics and computer science. In this talk, Professor Ouaknine considers three natural decision problems for LRS, namely the Skolem Problem (does a given LRS have a zero?), the Positivity Problem (are all terms of a given LRS positive?), and the Ultimate Positivity Problem (are all but finitely many terms of a given LRS positive?).

Such problems (and assorted variants) have applications in a wide array of scientific areas, such as theoretical biology (analysis of L-­systems, population dynamics), economics (stability of supply-­and-­demand equilibria in cyclical markets, multiplier-­accelerator models), software verification (termination of linear programs), probabilistic model checking (reachability and approximation in Markov chains, stochastic logics), quantum computing (threshold problems for quantum automata), discrete linear dynamical systems (reachability and invariance problems), as well as combinatorics, statistical physics, formal languages, etc.

Perhaps surprisingly, the study of decision problems for LRS involves advanced techniques from a variety of mathematical fields, including analytic and algebraic number theory, Diophantine geometry, and real algebraic geometry.

PDF Icon Event flyer