On Learning Polynomial Recursive Programs
summary
Introduces P-finite automata, a generalisation of weighted automata whose transition weights are polynomials in the input position and which over a unary alphabet compute P-finite (holonomic) sequences. Main claim: equivalence and Angluin MAT exact learning are polynomial-time learnable for this class. Construction uses a table of access/test words with polynomial interpolation, a module-based saturation algorithm to decide equivalence, and a reduction handling integer-weighted cases; all procedures run in time polynomial in the automaton size and max polynomial degree.
AI-written summary · about
chapters (7)
- 0:00Learning polynomial recursive programs
- 1:28Sequences recurrences and matrices
- 5:29Equivalence and learning results
- 7:18Learning Z weighted automata
- 9:24Equivalence for P finite automata
- 12:35Exact learning for P automata
- 15:06Q&A
related talks
11mProbabilistic Programming Meets Automata Theory: Exact Inference using Weighted Automata
55mLearning Safe Action Models
01h 23mAnalytic Methods for Supervised Learning I
25mLearning Formulas in Finite Variable Logics
43mControlling Probabilistic Systems Under Partial Observation
20mStatic Posterior Inference of Bayesian Probabilistic Programming via Polynomial Solving
34mA Polynomial Time Algorithm for Lossy Population Recovery
01h 06mAnalytic Methods for Supervised Learning III