On Polynomial Recursive Sequences

Cadilhac, Michaël; Mazowiecki, Filip; Paperman, Charles; Pilipczuk, Michał; Sénizergues, Géraud

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1007/s00224-021-10046-9

Titre :

On Polynomial Recursive Sequences

Auteur(s) :

Cadilhac, Michaël [Auteur]
School of Computing [DePaul] [SOC]
Mazowiecki, Filip [Auteur]
Max-Planck-Institut für Mathematik [MPI]
Paperman, Charles [Auteur]

Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Pilipczuk, Michał [Auteur]
Faculty of Mathematics, Informatics, and Mechanics [Warsaw] [MIMUW]
Sénizergues, Géraud [Auteur]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]

Titre de la revue :

Theory of Computing Systems

Éditeur :

Springer Verlag

Date de publication :

2021-06-02

ISSN :

1432-4350

Discipline(s) HAL :

Informatique [cs]/Théorie et langage formel [cs.FL]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :