EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On Polynomial Recursive Sequences

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

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

Expressive powerHigher-order pushdown automataRecursive sequencesWeighted automata

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}
}
Kostenlos starten →