You are not logged in | log in

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Automata Theory

 

n^n is not poly-recursive


Prelegent: Michał Pilipczuk

2019-10-30 14:15

A sequence (a_n)_{n\geq 0} is poly-recursive if there is a finite set of sequences,
one of them being (a_n)_{n\geq 0}, which can be defined using a system of recursive equations of the following form:
the nth entry of each sequence is equal to a polynomial of the (n-1)st entries of all the sequences.
We prove that the sequence a_n = n^n is not poly-recursive.

This is a joint work with Michaël Cadilhac, Charles Paperman, Filip Mazowiecki, and Géraud Sénizergues.