On Learning Polynomial Recursive Programs

Explore a groundbreaking 19-minute video presentation from the POPL 2024 conference introducing P-finite automata, a novel class of weighted automata with polynomial transition weights. Delve into the concept of these automata as simple tail-recursive programs and their relation to P-finite sequences. Discover the main research finding demonstrating that P-finite automata can be learned in polynomial time using Angluin's MAT exact learning model, extending classical results for deterministic finite automata and weighted automata. Gain insights into weighted automata, exact learning, holonomic sequences, and automata learning from experts Alex Buna-Marginean, Vincent Cheval, Mahsa Shirmohammadi, and James Worrell from the University of Oxford and CNRS - IRIF - Université Paris Cité.

[POPL'24] On Learning Polynomial Recursive Programs