EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On Learning Polynomial Recursive Programs

Alex Buna-Marginean, Vincent Cheval, Mahsa Shirmohammadi, James Worrell

Proceedings of the ACM on Programming Languages · 02.01.2024 · 8 (POPL) · 1001-1027

DOI: 10.1145/3632876 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 05.01.2024. Verfasst von Alex Buna-Marginean und 3 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: EPSRC Centre for Doctoral Training in Modern Statistics and Statistical Machine Learning, Agence Nationale de la Recherche, UKRI Frontier Research.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We introduce the class of P-finite automata. These are a generalisation of weighted automata, in which the weights of transitions can depend polynomially on the length of the input word. P-finite automata can also be viewed as simple tail-recursive programs in which the arguments of recursive calls can non-linearly refer to a variable that counts the number of recursive calls. The nomenclature is motivated by the fact that over a unary alphabet P-finite automata compute so-called P-finite sequences, that is, sequences that satisfy a linear recurrence with polynomial coefficients. Our main result shows that P-finite automata can be learned in polynomial time in Angluin’s MAT exact learning model. This generalises the classical results that deterministic finite automata and weighted automata over a field are respectively polynomial-time learnable in the MAT model.

Förderung

  • EPSRC Centre for Doctoral Training in Modern Statistics and Statistical Machine Learning
  • Agence Nationale de la Recherche
  • UKRI Frontier Research

Zitieren

APA

Buna-Marginean, A., Cheval, V., Shirmohammadi, M., & Worrell, J. (2024). On Learning Polynomial Recursive Programs. Proceedings of the ACM on Programming Languages, 8(POPL), 1001-1027. https://doi.org/10.1145/3632876

Vancouver

Buna-Marginean A, Cheval V, Shirmohammadi M, Worrell J. On Learning Polynomial Recursive Programs. Proceedings of the ACM on Programming Languages. 2024;8(POPL):1001-1027. doi:10.1145/3632876

BibTeX
@article{BunaMarginean2024,
  author = {Buna-Marginean, Alex and Cheval, Vincent and Shirmohammadi, Mahsa and Worrell, James},
  title = {On Learning Polynomial Recursive Programs},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {POPL},
  pages = {1001--1027},
  doi = {10.1145/3632876}
}
Kostenlos starten →