Evènement pour le groupe Séminaire Méthodes Formelles


Date 2020-04-21  14:00-15:00
TitreOn polynomial recursive sequences 
RésuméWe study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (non)expressiveness results translate to class separations. A typical example of a polynomial recursive sequence is b_n=n!. Our main result is that the sequence u_n=n^n is not polynomial recursive. This is joint work with Michaël Cadilhac, Charles Paperman, Michal Pilipczuk and Géraud Sénizergues available on arxiv https://arxiv.org/abs/2002.08630  
Lieuonline 
OrateurFilip Mazowiecki 
Emailhttps://fmazowiecki.github.io/ 
UrlMax Planck Institute for Software Systems 



Aucun document lié à cet événement.

Retour
Retour à l'index