Digital Security Group
Institute for Computing and Information Sciences
Radboud Universiteit Nijmegen
Tuesday, 9 June 2009, 14:00 (note the unusual weekday!)
Cybernetica Bldg (Akadeemia tee 21), room B101
Slides from the talk [pdf]
Abstract: In this talk we discuss non-linear recurrence relations with polynomial solutions. Such recurrent relations arise, for instance, in time and space complexity analysis of programs.
Contrary to linear recurrences, there is no general theory for solving non-linear equations. We notice that if we look for a polynomial solution and its possible degree is given, one can straightforwardly find this solution if exists, or establish absence of a polynomial solution of this degree, otherwise. We use the fact that any polynomial is defined by a finite number of points.
Thus, the main problem is to find the degree of a possible solution, given a recurrence. We study recurrences for which this problem is decidable.
(Joint work with Marko van Eekelen, Alejandro Tamalet.)