On Polynomial Recursive Sequences
Theory of Computing Systems · 2024-08 · 68 (4) · 593-614
DOI: 10.1007/s00224-021-10046-9 ↗Kurz gefasst
Fachartikel in der Zeitschrift Theory of Computing Systems, online erschienen am 02.06.2021. Verfasst von Michaël Cadilhac und 4 weiteren Autor:innen. Beteiligte Einrichtung: DePaul University, Chicago, IL 60484 USA. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 21 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council.
Abstract (Originalsprache)
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.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- DePaul University, Chicago, IL 60484 USA.
- Computer Science, MPI-SWS: Max-Planck-Institut fur Softwaresysteme, Campus E1 5, 66123 Saarbrücken, Germany.
- Université de Lille, Lille, France.
- University of Warsaw, Warsaw, Poland.
- Université de Bordeaux, Bordeaux, France.
ORCID-Profile: Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, Géraud Sénizergues
Förderung
- European Research Council
Zitieren
APA
Cadilhac, M., Mazowiecki, F., Paperman, C., Pilipczuk, M., & Sénizergues, G. (2024). On Polynomial Recursive Sequences. Theory of Computing Systems, 68(4), 593-614. https://doi.org/10.1007/s00224-021-10046-9
Vancouver
Cadilhac M, Mazowiecki F, Paperman C, Pilipczuk M, Sénizergues G. On Polynomial Recursive Sequences. Theory of Computing Systems. 2024;68(4):593-614. doi:10.1007/s00224-021-10046-9
BibTeX
@article{Cadilhac2024,
author = {Cadilhac, Michaël and Mazowiecki, Filip and Paperman, Charles and Pilipczuk, Michał and Sénizergues, Géraud},
title = {On Polynomial Recursive Sequences},
journal = {Theory of Computing Systems},
year = {2024},
volume = {68},
number = {4},
pages = {593--614},
doi = {10.1007/s00224-021-10046-9}
}
EUVIMED