{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T06:18:30Z","timestamp":1784873910831,"version":"3.55.0"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031308284","type":"print"},{"value":"9783031308291","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Fast matching of regular expressions with\n                    <jats:italic>bounded repetition<\/jats:italic>\n                    , aka\n                    <jats:italic>counting<\/jats:italic>\n                    , such as\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\texttt {(ab)\\{50,100\\}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>ab<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mo>{<\/mml:mo>\n                            <mml:mn>50<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mn>100<\/mml:mn>\n                            <mml:mo>}<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , i.e., matching linear in the length of the text and independent of the repetition bounds, has been an open problem for at least two decades. We show that, for a wide class of regular expressions with counting, which we call\n                    <jats:italic>synchronizing<\/jats:italic>\n                    , fast matching is possible. We empirically show that the class covers nearly all counting used in usual applications of regex matching. This complexity result is based on an improvement and analysis of a recent matching algorithm that compiles regexes to deterministic counting-set automata (automata with registers that hold sets of numbers).\n                  <\/jats:p>","DOI":"10.1007\/978-3-031-30829-1_19","type":"book-chapter","created":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T15:56:19Z","timestamp":1682006179000},"page":"392-412","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Fast Matching of Regular Patterns with Synchronizing Counting"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6957-1651","authenticated-orcid":false,"given":"Luk\u00e1\u0161","family":"Hol\u00edk","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7454-3751","authenticated-orcid":false,"given":"Juraj","family":"S\u00ed\u010d","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1450-6136","authenticated-orcid":false,"given":"Lenka","family":"Turo\u0148ov\u00e1","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2746-8792","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Vojnar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"19_CR1","unstructured":"Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools (2nd Edition). Addison Wesley (August 2006), http:\/\/www.amazon.ca\/exec\/obidos\/redirect?tag=citeulike09-20 &path=ASIN\/0321486811"},{"key":"19_CR2","doi-asserted-by":"publisher","unstructured":"Antimirov, V.: Partial derivatives of regular expressions and finite automaton constructions. Theoretical Computer Science 155(2), 291 \u2013 319 (1996). https:\/\/doi.org\/10.1016\/0304-3975(95)00182-4, https:\/\/doi.org\/10.1016\/0304-3975(95)00182-4","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"19_CR3","unstructured":"Baldwin, A.: Regular expression denial of service affecting express.js. https:\/\/medium.com\/node-security\/regular-expression-denial-of-service-affecting- express-js-9c397c164c43 (2016)"},{"key":"19_CR4","doi-asserted-by":"publisher","unstructured":"Bj\u00f6rklund, H., Martens, W., Timm, T.: Efficient incremental evaluation of succinct regular expressions. In: CIKM\u201915. ACM (2015). https:\/\/doi.org\/10.1145\/2806416.2806434","DOI":"10.1145\/2806416.2806434"},{"key":"19_CR5","doi-asserted-by":"publisher","unstructured":"Chapman, C., Stolee, K.T.: Exploring regular expression usage and context in python. In: Zeller, A., Roychoudhury, A. (eds.) Proceedings of the 25th International Symposium on Software Testing and Analysis, ISSTA 2016, Saarbr\u00fccken, Germany, July 18-20, 2016. pp. 282\u2013293. ACM (2016). https:\/\/doi.org\/10.1145\/2931037.2931073, https:\/\/doi.org\/10.1145\/2931037.2931073","DOI":"10.1145\/2931037.2931073"},{"key":"19_CR6","unstructured":"contributors, W.: Regular expression\u2014wikipedia (2019), https:\/\/en.wikipedia.org\/w\/index.php?title=Regular_expression &%20oldid=852858998"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"Davis, J.C.: Rethinking regex engines to address ReDoS. In: ESEC\/FSE\u201919. pp. 1256\u20131258. ACM (2019)","DOI":"10.1145\/3338906.3342509"},{"key":"19_CR8","doi-asserted-by":"publisher","unstructured":"Davis, J.C., Coghlan, C.A., Servant, F., Lee, D.: The impact of regular expression denial of service (redos) in practice: an empirical study at the ecosystem scale. In: Leavens, G.T., Garcia, A., Pasareanu, C.S. (eds.) Proceedings of the 2018 ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC\/SIGSOFT FSE 2018, Lake Buena Vista, FL, USA, November 04-09, 2018. pp. 246\u2013256. ACM (2018). https:\/\/doi.org\/10.1145\/3236024.3236027, https:\/\/doi.org\/10.1145\/3236024.3236027","DOI":"10.1145\/3236024.3236027"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Davis, J.C., Coghlan, C.A., Servant, F., Lee, D.: The impact of regular expression denial of service (ReDoS) in practice: An empirical study at the ecosystem scale. In: ESEC\/FSE\u201918. pp. 246\u2013256. ACM (2018)","DOI":"10.1145\/3236024.3236027"},{"key":"19_CR10","unstructured":"Davis, J.C., Michael\u00a0IV, L.G., Coghlan, C.A., Servant, F., Lee, D.: Why aren\u2019t regular expressions a lingua franca? An empirical study on the re-use and portability of regular expressions. In: ESEC\/FSE\u201919. pp. 1256\u20131258. ACM (2019)"},{"key":"19_CR11","doi-asserted-by":"publisher","unstructured":"Davis, J.C., Servant, F., Lee, D.: Using selective memoization to defeat regular expression denial of service (ReDoS). In: 42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021. pp. 1\u201317. IEEE (2021). https:\/\/doi.org\/10.1109\/SP40001.2021.00032, https:\/\/doi.org\/10.1109\/SP40001.2021.00032","DOI":"10.1109\/SP40001.2021.00032"},{"key":"19_CR12","unstructured":"docs.rs: regex - rust. https:\/\/docs.rs\/regex\/1.5.4\/regex\/ (2021)"},{"key":"19_CR13","unstructured":"Exchange, S.: Outage postmortem. http:\/\/stackstatus.net\/post\/147710624694\/outage-postmortem-july-20-2016 (2016)"},{"key":"19_CR14","doi-asserted-by":"publisher","unstructured":"Gelade, W., Gyssens, M., Martens, W.: Regular expressions with counting: Weak versus strong determinism. In: Mathematical Foundations of Computer Science 2009. pp. 369\u2013381. Springer Berlin Heidelberg, Berlin, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03816-7_32","DOI":"10.1007\/978-3-642-03816-7_32"},{"key":"19_CR15","doi-asserted-by":"publisher","unstructured":"Gelade, W., Gyssens, M., Martens, W.: Regular expressions with counting: Weak versus strong determinism. SIAM J. Comput. 41(1), 160\u2013190 (2012). https:\/\/doi.org\/10.1137\/100814196,extended version of paper in MFCS\u201909","DOI":"10.1137\/100814196"},{"key":"19_CR16","doi-asserted-by":"publisher","unstructured":"Glushkov, V.M.: The abstract theory of automata. Russian Math. Surveys 16, 1\u201353 (1961). https:\/\/doi.org\/10.1070\/RM1961v016n05ABEH004112","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"19_CR17","unstructured":"Google: RE2. https:\/\/github.com\/google\/re2"},{"key":"19_CR18","unstructured":"Graham-Cumming, J.: Details of the Cloudflare outage on july 2, 2019. https:\/\/blog.cloudflare.com\/details-of-the-cloudflare-outage-on-july-2-2019\/ (2019)"},{"key":"19_CR19","unstructured":"Haertel, M., et\u00a0al.: GNU grep. https:\/\/www.gnu.org\/software\/grep\/"},{"key":"19_CR20","doi-asserted-by":"publisher","unstructured":"Hol\u00edk, L., Leng\u00e1l, O., Saarikivi, O., Turo\u0148ov\u00e1, L., Veanes, M., Vojnar, T.: Succinct determinisation of counting automata via sphere construction. In: Proc. of APLAS\u201919. LNCS, vol. 11893, pp. 468\u2013489. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-34175-6_24","DOI":"10.1007\/978-3-030-34175-6_24"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"Hol\u00edk, L., S\u00ed\u010d, J., Turo\u0148ov\u00e1, L., Vojnar, T.: Fast matching of regular patterns with synchronizing counting (technical report). Tech. rep., Brno University of Technology (2023), https:\/\/doi.org\/10.48550\/arXiv.2301.12851","DOI":"10.1007\/978-3-031-30829-1_19"},{"key":"19_CR22","doi-asserted-by":"publisher","unstructured":"Hovland, D.: Regular expressions with numerical constraints and automata with counters. In: ICTAC. LNCS, vol.\u00a05684, pp. 231\u2013245. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-03466-4_15","DOI":"10.1007\/978-3-642-03466-4_15"},{"key":"19_CR23","doi-asserted-by":"publisher","unstructured":"Hovland, D.: The membership problem for regular expressions with unordered concatenation and numerical constraints. In: Language and Automata Theory and Applications. pp. 313\u2013324. Springer Berlin Heidelberg, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28332-1_27","DOI":"10.1007\/978-3-642-28332-1_27"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J., Seibert, S., Wilke, T.: Translating regular expressions into small $$\\epsilon $$-free nondeterministic finite automata. In: Reischuk, R., Morvan, M. (eds.) STACS 97. pp. 55\u201366. Springer Berlin Heidelberg, Berlin, Heidelberg (1997)","DOI":"10.1007\/BFb0023448"},{"key":"19_CR25","unstructured":"Kilpel\u00e4inen, P., Tuhkanen, R.: Regular expressions with numerical occurrence indicators - preliminary results. In: SPLST\u201903. pp. 163\u2013173. University of Kuopio, Department of Computer Science (2003)"},{"key":"19_CR26","doi-asserted-by":"publisher","unstructured":"Kilpel\u00e4inen, P., Tuhkanen, R.: One-unambiguity of regular expressions with numeric occurrence indicators. Information and Computation 205(6), 890\u2013916 (2007). https:\/\/doi.org\/10.1016\/j.ic.2006.12.003","DOI":"10.1016\/j.ic.2006.12.003"},{"key":"19_CR27","unstructured":"M. Roesch et al.: Snort: A Network Intrusion Detection and Prevention System,. http:\/\/www.snort.org"},{"key":"19_CR28","unstructured":"RegExLib.com: The Internet\u2019s first Regular Expression Library. http:\/\/regexlib.com\/"},{"key":"19_CR29","unstructured":"Robin Sommer et al.: The Bro Network Security Monitor, http:\/\/www.bro.org"},{"key":"19_CR30","doi-asserted-by":"publisher","unstructured":"Saarikivi, O., Veanes, M., Wan, T., Xu, E.: Symbolic regex matcher. In: Vojnar, T., Zhang, L. (eds.) TACAS\u20192019. LNCS, vol. 11427, pp. 372\u2013378. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-17462-0_24, https:\/\/doi.org\/10.1007\/978-3-030-17462-0_24","DOI":"10.1007\/978-3-030-17462-0_24"},{"key":"19_CR31","doi-asserted-by":"publisher","unstructured":"Smith, R., Estan, C., Jha, S.: XFA: faster signature matching with extended automata. In: IEEE Symposium on Security and Privacy. IEEE (2008). https:\/\/doi.org\/10.1109\/SP.2008.14","DOI":"10.1109\/SP.2008.14"},{"key":"19_CR32","doi-asserted-by":"publisher","unstructured":"Smith, R., Estan, C., Jha, S., Siahaan, I.: Fast signature matching using extended finite automaton (XFA). In: ICISS\u201908. LNCS, vol.\u00a05352, pp. 158\u2013172. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-540-89862-7_15","DOI":"10.1007\/978-3-540-89862-7_15"},{"key":"19_CR33","unstructured":"Sperberg-McQueen, M.: Notes on finite state automata with counters. https:\/\/www.w3.org\/XML\/2004\/05\/msm-cfa.html, https:\/\/www.w3.org\/XML\/2004\/05\/msm-cfa.html, accessed: 2018-08-08"},{"key":"19_CR34","unstructured":"The Sagan team: The Sagan Log Analysis Engine, https:\/\/quadrantsec.com\/sagan_log_analysis_engine\/"},{"key":"19_CR35","doi-asserted-by":"crossref","unstructured":"Thompson, K.: Programming techniques: Regular expression search algorithm. Commun. ACM 11(6), 419\u2013422 (1968)","DOI":"10.1145\/363347.363387"},{"key":"19_CR36","doi-asserted-by":"crossref","unstructured":"Turo\u0148ov\u00e1, L., Hol\u00edk, L., Leng\u00e1l, O., Saarikivi, O., Veanes, M., Vojnar, T.: Regex matching with counting-set automata. Proc. ACM Program. Lang. 4(OOPSLA), 218:1\u2013218:30 (2020)","DOI":"10.1145\/3428286"},{"key":"19_CR37","unstructured":"Turo\u0148ov\u00e1, L., Hol\u00edk, L., Leng\u00e1l, O., Veanes, M., Vojnar, T.: Counting in regexes considered harmful (2022)"},{"key":"19_CR38","doi-asserted-by":"publisher","unstructured":"\u010ce\u0161ka, M., Havlena, V., Hol\u00edk, L., Leng\u00e1l, O., Vojnar, T.: Approximate reduction of finite automata for high-speed network intrusion detection. In: Proc. of TACAS\u201918. LNCS, vol. 10806. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-89963-3_9","DOI":"10.1007\/978-3-319-89963-3_9"},{"key":"19_CR39","doi-asserted-by":"publisher","unstructured":"Wang, P., Stolee, K.T.: How well are regular expressions tested in the wild? In: Leavens, G.T., Garcia, A., Pasareanu, C.S. (eds.) Proceedings of the 2018 ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC\/SIGSOFT FSE 2018, Lake Buena Vista, FL, USA, November 04-09, 2018. pp. 668\u2013678. ACM (2018). https:\/\/doi.org\/10.1145\/3236024.3236072, https:\/\/doi.org\/10.1145\/3236024.3236072","DOI":"10.1145\/3236024.3236072"},{"key":"19_CR40","unstructured":"Wang, X., Hong, Y., Chang, H., Park, K., Langdale, G., Hu, J., Zhu, H.: Hyperscan: A fast multi-pattern regex matcher for modern CPUs. In: 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). pp. 631\u2013648. USENIX Association, Boston, MA (Feb 2019), https:\/\/www.usenix.org\/conference\/nsdi19\/presentation\/wang-xiang"},{"key":"19_CR41","unstructured":"W\u00fcbbeling, M.: Regular expression security. ADMIN 55 (2020)"},{"key":"19_CR42","doi-asserted-by":"crossref","unstructured":"Yang, L., Karim, R., Ganapathy, V., Smith, R.: Improving NFA-based signature matching using ordered binary decision diagrams. In: Recent Advances in Intrusion Detection. pp. 58\u201378. Springer Berlin Heidelberg (2010)","DOI":"10.1007\/978-3-642-15512-3_4"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30829-1_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T18:03:44Z","timestamp":1784829824000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30829-1_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031308284","9783031308291"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30829-1_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"21 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 April 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 April 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2023\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"85","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}