Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar by Prof. James Worrell (Oxford)

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
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 Skolem-Mahler-Lech 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.

Document Actions