LFCS Seminar by Prof. James Worrell (Oxford)
Positivity Problems for Linear Recurrence Sequences
What 


When 
Dec 02, 2014 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Contact Name  Kousha Etessami 
Add event to calendar 
vCal iCal 
The Positivity Problem asks whether all terms of a given linear recurrence sequence are positive. Linear recurrence sequences are ubiquitous and this decision problem arises in many settings, including formal languages, population dynamics, probabilistic model checking, loop termination, and combinatorics. It is also closely related to the SkolemMahlerLech Theorem in number theory, which describes the set of zeros of a linear recurrence sequence.
The Positivity Problem has been studied since the 1970s; however its decidability remains open. In this talk I will discuss the history and significance of this and related problems, some recent positive decidability results, and obstacles to further progress.