{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T03:12:00Z","timestamp":1783653120364,"version":"3.55.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T00:00:00Z","timestamp":1704153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"EPSRC Centre for Doctoral Training in Modern Statistics and Statistical Machine Learning","award":["EP\/S023151\/1"],"award-info":[{"award-number":["EP\/S023151\/1"]}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-22- CE48-0005, ANR-CREST-JST"],"award-info":[{"award-number":["ANR-22- CE48-0005, ANR-CREST-JST"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"UKRI Frontier Research","award":["EP\/X033813\/1"],"award-info":[{"award-number":["EP\/X033813\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,1,2]]},"abstract":"<jats:p>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\u2019s 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.<\/jats:p>","DOI":"10.1145\/3632876","type":"journal-article","created":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T20:48:51Z","timestamp":1704487731000},"page":"1001-1027","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["On Learning Polynomial Recursive Programs"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-0750-445X","authenticated-orcid":false,"given":"Alex","family":"Buna-Marginean","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3622-2129","authenticated-orcid":false,"given":"Vincent","family":"Cheval","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7779-2339","authenticated-orcid":false,"given":"Mahsa","family":"Shirmohammadi","sequence":"additional","affiliation":[{"name":"CNRS - IRIF - Universit\u00e9 Paris Cit\u00e9, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8151-2443","authenticated-orcid":false,"given":"James","family":"Worrell","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,5]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1026"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30162-4_194"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005101"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/52107"},{"key":"e_1_3_1_7_1","volume-title":"Encyclopedia of Mathematics and its Applications","author":"Berstel Jean","year":"2010","unstructured":"Jean Berstel and Christophe Reutenauer. 2010. . Encyclopedia of Mathematics and its Applications, Vol. 137. Cambridge University Press."},{"key":"e_1_3_1_8_1","unstructured":"Benedikt Bollig Peter Habermehl Carsten Kern and Martin Leucker. 2009. Angluin-Style Learning of NFA. In IFCAI 2009 Proceedings of the 21st International Joint Conference on Artificial Intelligence. 1004\u20131009."},{"key":"e_1_3_1_9_1","doi-asserted-by":"crossref","unstructured":"Benedikt Bollig Joost-Pieter Katoen Carsten Kern Martin Leucker Daniel Neider and David R. Piegdon. 2010. libalf: The Automata Learning Framework. In CAV 2010 (LNCS Vol. 6174). Springer Edinburgh UK 360\u2013364.","DOI":"10.1007\/978-3-642-14295-6_32"},{"key":"e_1_3_1_10_1","doi-asserted-by":"crossref","unstructured":"Alex Buna-Marginean Vincent Cheval Mahsa Shirmohammadi and James Worrell. 2023. On Learning Polynomial Recursive Programs. arXiv:2310.14725 [cs.LO]","DOI":"10.1145\/3632876"},{"issue":"9","key":"e_1_3_1_11_1","first-page":"197","article-title":"Matrices de hankel","volume":"53","author":"Fliess Michel","year":"1974","unstructured":"Michel Fliess. 1974. Matrices de hankel. J. Math. Pures Appl 53, 9 (1974), 197\u2013222.","journal-title":"J. Math. Pures Appl"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91908-9_26"},{"key":"e_1_3_1_13_1","doi-asserted-by":"crossref","unstructured":"Andreas Humenberger Maximilian Jaroschek and Laura Kov\u00e1cs. 2017a. Automated generation of non-linear loop invariants utilizing hypergeometric sequences. In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation. 221\u2013228.","DOI":"10.1145\/3087604.3087623"},{"key":"e_1_3_1_14_1","first-page":"226","volume-title":"International Conference on Verification, Model Checking, and Abstract Interpretation","author":"Humenberger Andreas","year":"2017","unstructured":"Andreas Humenberger, Maximilian Jaroschek, and Laura Kov\u00e1cs. 2017b. Invariant generation for multi-path loops with polynomial assignments. In International Conference on Verification, Model Checking, and Abstract Interpretation. Springer, 226\u2013246."},{"key":"e_1_3_1_15_1","doi-asserted-by":"crossref","unstructured":"Malte Isberner Falk Howar and Bernhard Steffen. 2015. The Open-Source LearnLib - A Framework for Active Automata Learning. In CAV 2015 (LNCS Vol. 9206). Springer San Francisco CA USA 487\u2013495.","DOI":"10.1007\/978-3-319-21690-4_32"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90131-8"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1983480"},{"key":"e_1_3_1_18_1","unstructured":"Stefan Kiefer. 2020. Notes on Equivalence and Minimization of Weighted Automata. arXiv:2009.01217 [cs.FL]"},{"key":"e_1_3_1_19_1","doi-asserted-by":"crossref","unstructured":"Laura Kov\u00e1cs. 2008. Reasoning Algebraically About P-Solvable Loops. In Tools and Algorithms for the Construction and Analysis of Systems 14th International Conference TACAS Proceedings (Lecture Notes in Computer Science Vol. 4963). Springer 249\u2013264.","DOI":"10.1007\/978-3-540-78800-3_18"},{"key":"e_1_3_1_20_1","unstructured":"Jakub Michaliszyn and Jan Otop. 2022. Learning Deterministic Visibly Pushdown Automata Under Accessible Stack. In 47th International Symposium on Mathematical Foundations of Computer Science MFCS (LIPIcs Vol. 241). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik 74:1\u201374:16."},{"key":"e_1_3_1_21_1","doi-asserted-by":"crossref","unstructured":"Joshua Moerman Matteo Sammartino Alexandra Silva Bartek Klin and Michal Szynwelski. 2017. Learning nominal automata. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages POPL. ACM 613\u2013625.","DOI":"10.1145\/3009837.3009879"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(96)00163-2"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.37236\/2721"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(61)80020-X"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1098\/rstl.1861.0016"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221017"},{"key":"e_1_3_1_27_1","doi-asserted-by":"crossref","unstructured":"Gerco van Heerdt Clemens Kupke Jurriaan Rot and Alexandra Silva. 2020. Learning Weighted Automata over Principal Ideal Domains. In Foundations of Software Science and Computation Structures - 23rd International Conference FOSSACS 2020 Proceedings (Lecture Notes in Computer Science Vol. 12077). Springer 602\u2013621.","DOI":"10.1007\/978-3-030-45231-5_31"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632876","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632876","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:07:15Z","timestamp":1751659635000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632876"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,2]]},"references-count":26,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2024,1,2]]}},"alternative-id":["10.1145\/3632876"],"URL":"https:\/\/doi.org\/10.1145\/3632876","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,2]]},"assertion":[{"value":"2024-01-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}