{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T00:19:24Z","timestamp":1706573964566},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","funder":[{"name":"EPSRC Centre for Doctoral Training in Modern Statistics and Statistical Machine Learning","award":["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"]},{"name":"UKRI Frontier Research","award":["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,5]]},"abstract":"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.<\/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":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On Learning Polynomial Recursive Programs"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"http:\/\/orcid.org\/0009-0005-0750-445X","authenticated-orcid":false,"given":"Alex","family":"Buna-Marginean","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-3622-2129","authenticated-orcid":false,"given":"Vincent","family":"Cheval","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}]},{"ORCID":"http:\/\/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"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-8151-2443","authenticated-orcid":false,"given":"James","family":"Worrell","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}]}],"member":"320","published-online":{"date-parts":[[2024,1,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1026"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30162-4_194"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005101"},{"key":"e_1_2_1_5_1","volume-title":"Rational series and their languages. 12","author":"Berstel Jean","unstructured":"Jean Berstel and Christophe Reutenauer. 1988. Rational series and their languages. 12, Springer-Verlag."},{"key":"e_1_2_1_6_1","unstructured":"Jean Berstel and Christophe Reutenauer. 2010. Cambridge University Press."},{"key":"e_1_2_1_7_1","volume-title":"Angluin-Style Learning of NFA. In IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence. 1004\u20131009","author":"Bollig Benedikt","year":"2009","unstructured":"Benedikt Bollig, Peter Habermehl, Carsten Kern, and Martin Leucker. 2009. Angluin-Style Learning of NFA. In IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence. 1004\u20131009."},{"key":"e_1_2_1_8_1","volume-title":"CAV 2010 (LNCS","volume":"364","author":"Bollig Benedikt","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."},{"key":"e_1_2_1_9_1","unstructured":"Alex Buna-Marginean Vincent Cheval Mahsa Shirmohammadi and James Worrell. 2023. On Learning Polynomial Recursive Programs. arxiv:2310.14725."},{"key":"e_1_2_1_10_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_2_1_11_1","volume-title":"Vaandrager","author":"Howar Falk","year":"2019","unstructured":"Falk Howar, Bengt Jonsson, and Frits W. Vaandrager. 2019. Combining Black-Box and White-Box Techniques for Learning Register Automata. In Computing and Software Science - State of the Art and Perspectives (LNCS, Vol. 10000). Springer, Cham. 563\u2013588."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087604.3087623"},{"key":"e_1_2_1_13_1","volume-title":"International Conference on Verification, Model Checking, and Abstract Interpretation. 226\u2013246","author":"Humenberger Andreas","year":"2017","unstructured":"Andreas Humenberger, Maximilian Jaroschek, and Laura Kov\u00e1cs. 2017. Invariant generation for multi-path loops with polynomial assignments. In International Conference on Verification, Model Checking, and Abstract Interpretation. 226\u2013246."},{"key":"e_1_2_1_14_1","volume-title":"The Open-Source LearnLib - A Framework for Active Automata Learning. In CAV 2015 (LNCS","volume":"495","author":"Isberner Malte","year":"2015","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."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90131-8"},{"key":"e_1_2_1_16_1","volume-title":"The Concrete Tetrahedron","author":"Kauers Manuel","unstructured":"Manuel Kauers and Peter Paule. 2011. The Concrete Tetrahedron (1st ed.). Springer Wien.","edition":"1"},{"key":"e_1_2_1_17_1","unstructured":"Stefan Kiefer. 2020. Notes on Equivalence and Minimization of Weighted Automata. arxiv:2009.01217."},{"key":"e_1_2_1_18_1","volume-title":"14th International Conference, TACAS, Proceedings (Lecture Notes in Computer Science","volume":"264","author":"Kov\u00e1cs Laura","year":"2008","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."},{"key":"e_1_2_1_19_1","volume-title":"Learning Deterministic Visibly Pushdown Automata Under Accessible Stack. In 47th International Symposium on Mathematical Foundations of Computer Science, MFCS (LIPIcs","volume":"16","author":"Michaliszyn Jakub","year":"2022","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_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009879"},{"key":"e_1_2_1_21_1","volume-title":"The Smith normal form. Linear algebra and its applications, 254, 1-3","author":"Newman Morris","year":"1997","unstructured":"Morris Newman. 1997. The Smith normal form. Linear algebra and its applications, 254, 1-3 (1997), 367\u2013381."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.37236\/2721"},{"key":"e_1_2_1_23_1","first-page":"2","article-title":"On the Definition of a Family of","volume":"4","author":"Sch\u00fctzenberger Marcel Paul","year":"1961","unstructured":"Marcel Paul Sch\u00fctzenberger. 1961. On the Definition of a Family of Automata. Inf. Control., 4, 2-3 (1961), 245\u2013270.","journal-title":"Automata. Inf. Control."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1098\/rstl.1861.0016"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221017"},{"key":"e_1_2_1_26_1","volume-title":"FOSSACS 2020, Proceedings (Lecture Notes in Computer Science","volume":"621","author":"van Heerdt Gerco","year":"2020","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."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632876","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,29]],"date-time":"2024-01-29T15:17:46Z","timestamp":1706541466000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632876"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,5]]},"references-count":26,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2024,1,5]]}},"alternative-id":["10.1145\/3632876"],"URL":"http:\/\/dx.doi.org\/10.1145\/3632876","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,5]]},"assertion":[{"value":"2024-01-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}