{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T11:16:29Z","timestamp":1783509389601,"version":"3.55.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031986819","type":"print"},{"value":"9783031986826","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T00:00:00Z","timestamp":1753228800000},"content-version":"vor","delay-in-days":203,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We introduce a high-level language with Python-like syntax for string-to-string, polyregular, first-order definable transductions. This language features function calls, boolean variables, and nested for-loops. We devise and implement a complete decision procedure for the verification of such programs against a first-order specification. The decision procedure reduces the verification problem to the decidable first-order theory of finite words (extensively studied in automata theory), which we discharge using either complete tools specific to this theory (MONA), or to general-purpose SMT solvers (Z3, CVC5).<\/jats:p>","DOI":"10.1007\/978-3-031-98682-6_1","type":"book-chapter","created":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T03:14:54Z","timestamp":1753154094000},"page":"3-25","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Polyregular Model Checking"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4205-327X","authenticated-orcid":false,"given":"Aliaume","family":"Lopez","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8439-4056","authenticated-orcid":false,"given":"Rafa\u0142","family":"Stefa\u0144ski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,7,23]]},"reference":[{"key":"1_CR1","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-20920-8_1","volume-title":"Logic, Language, Information and Computation","author":"R Alur","year":"2011","unstructured":"Alur, R.: Streaming string transducers. In: Beklemishev, L.D., de Queiroz, R. (eds.) WoLLIC 2011. LNCS (LNAI), vol. 6642, pp. 1\u20131. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20920-8_1"},{"key":"1_CR2","doi-asserted-by":"publisher","unstructured":"Alur, R., \u010cern\u00fd, P.: Streaming transducers for algorithmic verification of single-pass list-processing programs. In: Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL \u201911, pp. 599\u2013610. Association for Computing Machinery, New York (2011). https:\/\/doi.org\/10.1145\/1926385.1926454","DOI":"10.1145\/1926385.1926454"},{"key":"1_CR3","unstructured":"Barrett, C., Fontaine, P., Tinelli, C.: The SMT-LIB Standard: Version 2.6. Technical report, Department of Computer Science, The University of Iowa (2017). www.SMT-LIB.org"},{"key":"1_CR4","unstructured":"Bobot, F., Filli\u00e2tre, J.C., March\u00e9, C., Paskevich, A.: Why3: shepherd your herd of provers. In: Boogie 2011: First International Workshop on Intermediate Verification Languages, Wroc\u0142aw, Poland, pp. 53\u201364 (2011). https:\/\/hal.inria.fr\/hal-00790310"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M.: On the growth rates of polyregular functions. In: 2023 38th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS), pp. 1\u201313. IEEE (2023)","DOI":"10.1109\/LICS56636.2023.10175808"},{"key":"1_CR6","unstructured":"Boja\u0144czyk, M., Kiefer, S., Lhote, N.: String-to-string interpretations with polynomial-size output. arXiv preprint arXiv:1905.13190 (2019)"},{"key":"1_CR7","unstructured":"Boja\u0144czyk, M.: Polyregular functions (2018). https:\/\/arxiv.org\/abs\/1810.08760v1"},{"key":"1_CR8","unstructured":"Boja\u0144czyk, M.: Slightly infinite sets (2019). https:\/\/www.mimuw.edu.pl\/~bojan\/paper\/atom-book"},{"key":"1_CR9","doi-asserted-by":"publisher","unstructured":"Boja\u0144czyk, M., Daviaud, L., Krishna, S.N.: Regular and first-order list functions. In: Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS \u201918, pp. 125\u2013134. Association for Computing Machinery, New York (2018). https:\/\/doi.org\/10.1145\/3209108.3209163","DOI":"10.1145\/3209108.3209163"},{"key":"1_CR10","doi-asserted-by":"publisher","unstructured":"de\u00a0Bruijn, N.: Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the church-rosser theorem. Indagationes Mathematicae (Proceedings) 75(5), 381\u2013392 (1972). https:\/\/doi.org\/10.1016\/1385-7258(72)90034-0","DOI":"10.1016\/1385-7258(72)90034-0"},{"issue":"1\u20136","key":"1_CR11","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"JR B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Math. Log. Q. 6(1\u20136), 66\u201392 (1960). https:\/\/doi.org\/10.1002\/malq.19600060105","journal-title":"Math. Log. Q."},{"key":"1_CR12","doi-asserted-by":"publisher","unstructured":"Carton, O., Dartois, L.: Aperiodic two-way transducers and FO-transductions. In: Kreutzer, S. (ed.) 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a041, pp. 160\u2013174. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2015). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2015.160","DOI":"10.4230\/LIPIcs.CSL.2015.160"},{"key":"1_CR13","doi-asserted-by":"publisher","unstructured":"Chen, T., Hague, M., Lin, A.W., R\u00fcmer, P., Wu, Z.: Decision procedures for path feasibility of string-manipulating programs with complex operations. Proc. ACM Program. Lang. 3(POPL) (2019). https:\/\/doi.org\/10.1145\/3290362. http:\/\/www.philipp.ruemmer.org\/publications\/atva2020.pdf","DOI":"10.1145\/3290362"},{"key":"1_CR14","doi-asserted-by":"publisher","unstructured":"Duret-Lutz, A., et al.: From Spot 2.0 to Spot 2.10: what\u2019s new? In: Proceedings of the 34th International Conference on Computer Aided Verification (CAV\u201922). Lecture Notes in Computer Science, vol. 13372, pp. 174\u2013187. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-031-13188-2_9","DOI":"10.1007\/978-3-031-13188-2_9"},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-319-63387-9_3","volume-title":"Computer Aided Verification","author":"L D\u2019Antoni","year":"2017","unstructured":"D\u2019Antoni, L., Veanes, M.: The power of symbolic automata and transducers. In: Majumdar, R., Kun\u010dak, V. (eds.) CAV 2017. LNCS, vol. 10426, pp. 47\u201367. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63387-9_3"},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-45687-2_19","volume-title":"Mathematical Foundations of Computer Science 2002","author":"J Engelfriet","year":"2002","unstructured":"Engelfriet, J., Maneth, S.: Two-way finite state transducers with nested pebbles. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 234\u2013244. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45687-2_19"},{"key":"1_CR17","unstructured":"Filiot, E., Reynier, P.A., Lhote, N.: Lexicographic transductions of finite words (2025). https:\/\/arxiv.org\/abs\/2503.01746"},{"key":"1_CR18","doi-asserted-by":"publisher","unstructured":"Je\u017c, A., Lin, A.W., Markgraf, O., R\u00fcmmer, P.: Decision procedures for sequence theories. In: Computer Aided Verification: 35th International Conference, CAV 2023, Paris, France, July 17\u201322, 2023, Proceedings, Part II, CAV\u201923, pp. 18\u201340. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-37703-7_2. https:\/\/anthonywlin.github.io\/papers\/cav23.pdf","DOI":"10.1007\/978-3-031-37703-7_2"},{"key":"1_CR19","doi-asserted-by":"publisher","unstructured":"Kaminski, M., Francez, N.: Finite-memory automata. Theor. Comput. Sci. 134(2), 329\u2013363 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90242-9","DOI":"10.1016\/0304-3975(94)90242-9"},{"key":"1_CR20","unstructured":"Klarlund, N., M\u00f8ller, A.: MONA Version 1.4 User Manual. BRICS, Department of Computer Science, University of Aarhus (2001), notes Series NS-01-1. http:\/\/www.brics.dk\/mona\/"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1515\/9781400882618-002","volume":"34","author":"SC Kleene","year":"1956","unstructured":"Kleene, S.C.: Representation of events in nerve nets and finite automata. Automata Stud. 34, 3\u201342 (1956). https:\/\/doi.org\/10.1515\/9781400882618-002","journal-title":"Automata Stud."},{"key":"1_CR22","doi-asserted-by":"publisher","DOI":"10.5555\/1097043","volume-title":"Counter-Free Automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.A.: Counter-Free Automata. The MIT Press, Cambridge (1971). https:\/\/doi.org\/10.5555\/1097043"},{"key":"1_CR23","unstructured":"Microsoft Research: Z3 theorem prover (2008). https:\/\/github.com\/Z3Prover\/z3, swh:1:dir:d6e5b24a3751b89fb1a4844c5a80a6393c2c1fa6"},{"key":"1_CR24","doi-asserted-by":"publisher","unstructured":"Muscholl, A., Puppis, G.: The many facets of string transducers. In: Niedermeier, R., Paul, C. (eds.) 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0126, pp. 2:1\u20132:21. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.2. https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.STACS.2019.2","DOI":"10.4230\/LIPIcs.STACS.2019.2"},{"key":"1_CR25","doi-asserted-by":"publisher","unstructured":"Perrin, D., Pin, J.\u00c9.: First-order logic and star-free sets. J. Comput. Syst. Sci. 32(3), 393\u2013406 (1986). https:\/\/doi.org\/10.1016\/0022-0000(86)90037-1. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0022000086900371","DOI":"10.1016\/0022-0000(86)90037-1"},{"key":"1_CR26","doi-asserted-by":"publisher","unstructured":"Rabin, M.O., Scott, D.S.: Finite automata and their decision problems. IBM J. Res. Dev. 3(2), 114\u2013125 (1959). https:\/\/doi.org\/10.1147\/RD.32.0114","DOI":"10.1147\/RD.32.0114"},{"key":"1_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/3-540-36387-4_13","volume-title":"Automata Logics, and Infinite Games","author":"K Reinhardt","year":"2002","unstructured":"Reinhardt, K.: The complexity of translating logic to finite automata. In: Gr\u00e4del, E., Thomas, W., Wilke, T. (eds.) Automata Logics, and Infinite Games. LNCS, vol. 2500, pp. 231\u2013238. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-36387-4_13"},{"issue":"2\u20133","key":"1_CR28","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0019-9958(61)80020-X","volume":"4","author":"MP Sch\u00fctzenberger","year":"1961","unstructured":"Sch\u00fctzenberger, M.P.: On the definition of a family of automata. Inf. Control 4(2\u20133), 245\u2013270 (1961). https:\/\/doi.org\/10.1016\/S0019-9958(61)80020-X","journal-title":"Inf. Control"},{"issue":"2","key":"1_CR29","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"MP Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.P.: On finite monoids having only trivial subgroups. Inf. Control 8(2), 190\u2013194 (1965). https:\/\/doi.org\/10.1016\/S0019-9958(65)90108-7","journal-title":"Inf. Control"},{"issue":"2","key":"1_CR30","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1090\/trans2\/059\/02","volume":"59","author":"BA Trakhtenbrot","year":"1966","unstructured":"Trakhtenbrot, B.A.: Finite automata and the logic of one-place predicates. Am. Math. Soc. Translat. 59(2), 23\u201355 (1966). https:\/\/doi.org\/10.1090\/trans2\/059\/02","journal-title":"Am. Math. Soc. Translat."},{"key":"1_CR31","doi-asserted-by":"publisher","unstructured":"Winskel, G.: The Formal Semantics of Programming Languages: An Introduction. MIT Press, Cambridge (1993). https:\/\/doi.org\/10.7551\/mitpress\/3054.001.0001","DOI":"10.7551\/mitpress\/3054.001.0001"},{"key":"1_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/978-3-030-99524-9_24","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"H Barbosa","year":"2022","unstructured":"Barbosa, H., et al.: cvc5: a versatile and industrial-strength SMT solver. In: Fisman, D., Rosu, G., et al. (eds.) TACAS 2022. LNCS, vol. 13243, pp. 415\u2013442. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-99524-9_24"}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-98682-6_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T10:32:20Z","timestamp":1783506740000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-98682-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031986819","9783031986826"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-98682-6_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"23 July 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CAV","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Computer Aided Verification","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Zagreb","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Croatia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 July 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cav2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conferences.i-cav.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}