{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,19]],"date-time":"2026-08-19T19:01:19Z","timestamp":1787166079321,"version":"build-2736575974"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,4,29]]},"abstract":"<jats:p>A common problem in string constraint solvers is computing the Parikh image, a linear arithmetic formula that describes all possible combinations of character counts in strings of a given language. Automata-based string solvers frequently need to compute the Parikh image of products (or intersections) of finite-state automata, in particular when solving string constraints that also include the integer data-type due to operations like string length and indexing. In this context, the computation of Parikh images often turns out to be both prohibitively slow and memory-intensive. This paper contributes a new understanding of how the reasoning about Parikh images can be cast as a constraint solving problem, and questions about Parikh images be answered without explicitly computing the product automaton or the exact Parikh image. The paper shows how this formulation can be efficiently implemented as a calculus, PC*, embedded in an automated theorem prover supporting Presburger logic. The resulting standalone tool Catra is evaluate on constraints produced by the Ostrich+ string solver when solving standard string constraint benchmarks involving integer operations. The experiments show that PC* strictly outperforms the standard approach by Verma et al. to extract Parikh images from finite-state automata, as well as the over-approximating method recently described by Jank\u016f and Turo\u0148ov\u00e1 by a wide margin, and for realistic timeouts (under 60 s) also the nuXmv model checker. When added as the Parikh image backend of Ostrich+ to the Ostrich string constraint solver\u2019s portfolio, it boosts its results on the quantifier-free strings with linear integer algebra track of SMT-COMP 2023 (QF_SLIA) enough to solve the most Unsat instances in that track of all competitors.<\/jats:p>","DOI":"10.1145\/3649855","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T13:53:50Z","timestamp":1714398830000},"page":"1235-1263","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Constraint Solving Approach to Parikh Images of Regular Languages"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4180-6118","authenticated-orcid":false,"given":"Amanda","family":"Stjerna","sequence":"first","affiliation":[{"name":"Uppsala University, Uppsala, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2733-7098","authenticated-orcid":false,"given":"Philipp","family":"R\u00fcmmer","sequence":"additional","affiliation":[{"name":"University of Regensburg, Regensburg, Germany \/ Uppsala University, Uppsala, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062384"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21690-4_29"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99524-9_24"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.23919\/FMCAD.2017.8102241"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81688-9_14"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68670-7"},{"key":"e_1_2_1_7_1","unstructured":"Micha\u00ebl Cadilhac Alain Finkel and Pierre McKenzie. 2011. On the expressiveness of Parikh automata and related models. arxiv:1101.1547."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_22"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59152-6_18"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290362"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.03.019"},{"key":"e_1_2_1_13_1","volume-title":"Path Logics for Querying Graphs: Combining Expressiveness and Efficiency. In 2015 30th Annual ACM\/IEEE Symposium on Logic in Computer Science. IEEE","author":"Figueira Diego","year":"2015","unstructured":"Diego Figueira and Leonid Libkin. 2015. Path Logics for Querying Graphs: Combining Expressiveness and Efficiency. In 2015 30th Annual ACM\/IEEE Symposium on Logic in Computer Science. IEEE, Kyoto, Japan. 329\u2013340. https:\/\/doi.org\/10.1109\/LICS.2015.39 10.1109\/LICS.2015.39"},{"key":"e_1_2_1_14_1","volume-title":"First-Order Logic and Automated Theorem Proving","author":"Fitting Melvin C.","unstructured":"Melvin C. Fitting. 1996. First-Order Logic and Automated Theorem Proving (2nd ed.). Springer-Verlag, New York, NY, USA. isbn:978-1-4612-7515-2","edition":"2"},{"key":"e_1_2_1_15_1","volume-title":"Handbook of Practical Logic and Automated Reasoning","author":"Harrison John","unstructured":"John Harrison. 2009. Handbook of Practical Logic and Automated Reasoning. Cambridge University Press, Shaftesbury Road, Cambridge, UK. isbn:978-0-521-89957-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158092"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45093-9_59"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(80)90493-3"},{"key":"e_1_2_1_19_1","unstructured":"Felix Klaedtke and Harald Rue\u00df. 2002. Parikh Automata and Monadic Second-Order Logics with Linear Cardinality Constraints. Albert-Ludwigs-Universit\u00e4t Freiburg. https:\/\/tr.informatik.uni-freiburg.de\/reports\/report177\/report00177.ps.gz"},{"key":"e_1_2_1_20_1","volume-title":"Automata and computability","author":"Kozen Dexter C.","unstructured":"Dexter C. Kozen. 1997. Automata and computability. Springer, New York. isbn:0387949070"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.06.003"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90029-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-90870-6_21"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321364"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Rodrigo Raya. 2023. Decision Procedures for Power Structures. Ph. D. Dissertation. EPFL. Lausanne. https:\/\/doi.org\/10.5075\/epfl-thesis-10546 10.5075\/epfl-thesis-10546","DOI":"10.5075\/epfl-thesis-10546"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_24"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89439-1_20"},{"key":"e_1_2_1_29_1","volume-title":"2010 IEEE Symposium on Security and Privacy. IEEE","author":"Saxena Prateek","year":"2010","unstructured":"Prateek Saxena, Devdatta Akhawe, Steve Hanna, Feng Mao, Stephen McCamant, and Dawn Song. 2010. A Symbolic Execution Framework for JavaScript. In 2010 IEEE Symposium on Security and Privacy. IEEE, Oakland, CA, USA. 513\u2013528. https:\/\/doi.org\/10.1109\/SP.2010.38 10.1109\/SP.2010.38"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_94"},{"key":"e_1_2_1_31_1","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"Siromoney Rani","unstructured":"Rani Siromoney and V. Rajkumar Dare. 1985. A generalization of the Parikh vector for finite and infinite words. In Foundations of Software Technology and Theoretical Computer Science, S. N. Maheshwari (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 290\u2013302. isbn:978-3-540-39722-9"},{"key":"e_1_2_1_32_1","unstructured":"SMT-COMP. 2023. SMT-COMP 2023 Results. https:\/\/smt-comp.github.io\/2023\/results.html"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3463952.3464097"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454066"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","unstructured":"Amanda Stjerna and Philipp R\u00fcmmer. 2024. Reproduction Package for \u2018A Constraint Solving Approach to Parikh Images of Regular Languages\u2019. https:\/\/doi.org\/10.5281\/zenodo.10796555 10.5281\/zenodo.10796555","DOI":"10.5281\/zenodo.10796555"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11532231_25"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering (ESEC\/FSE","author":"Zheng Yunhui","year":"2013","unstructured":"Yunhui Zheng, Xiangyu Zhang, and Vijay Ganesh. 2013. Z3-str: a z3-based string solver for web application analysis. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering (ESEC\/FSE 2013). Association for Computing Machinery, New York, NY, USA. 114\u2013124. isbn:9781450322379 https:\/\/doi.org\/10.1145\/2491411.2491456 10.1145\/2491411.2491456"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649855","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649855","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:54:07Z","timestamp":1750272847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649855"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":37,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2024,4,29]]}},"alternative-id":["10.1145\/3649855"],"URL":"https:\/\/doi.org\/10.1145\/3649855","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"2024-04-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}