Publication Details

Regex Matching with Counting-Set Automata

HOLÍKOVÁ Lenka, HOLÍK Lukáš, LENGÁL Ondřej, SAARIKIVI Olli, VEANES Margus and VOJNAR Tomáš. Regex Matching with Counting-Set Automata. Proceedings of the ACM on Programming Languages, vol. 4, no. 11, 2020, pp. 1-30. ISSN 2475-1421. Available from: https://www.microsoft.com/en-us/research/uploads/prod/2020/09/MSR-TR-2020-31.pdf
Czech title
Hledání regulárních výrazů za pomocí automatů s čítačovými registry
Type
journal article
Language
english
Authors
Holíková Lenka, Ing. (DITS FIT BUT)
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT)
Lengál Ondřej, Ing., Ph.D. (DITS FIT BUT)
Saarikivi Olli (MSR)
Veanes Margus (MSR)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT)
URL
Keywords

regular expression matching, bounded repetition, ReDos, determinization, Antimirovs derivatives, counting automata, counting-set automata

Abstract

We propose a solution to the problem of efficient matching regular expressions (regexes) with bounded repetition, such as (ab){1,100}, using deterministic automata. For this, we introduce novel counting-set automata (CsAs), automata with registers that can hold sets of bounded integers and can be manipulated by a limited portfolio of constant-time operations. We present an algorithm that compiles a large sub-class of regexes to deterministic CsAs. This includes (1) a novel Antimirov-style translation of regexes with counting to counting automata (CAs), nondeterministic automata with bounded counters, and (2) our main technical contribution, a determinization of CAs that outputs CsAs. The main advantage of this workflow is that the size of the produced CsAs does not depend on the repetition bounds used in the regex (while the size of the DFA is exponential to them). Our experimental results confirm that deterministic CsAs produced from practical regexes with repetition are indeed vastly smaller than the corresponding DFAs. More importantly, our prototype matcher based on CsA simulation handles practical regexes with repetition regardless of sizes of counter bounds. It easily copes with regexes with repetition where state-of-the-art matchers struggle.

Published
2020
Pages
1-30
Journal
Proceedings of the ACM on Programming Languages, vol. 4, no. 11, ISSN 2475-1421
Publisher
Association for Computing Machinery
DOI
10.1145/3428286
UT WoS
000685203900095
EID Scopus
2-s2.0-85097577301
BibTeX 
@ARTICLE{FITPUB12388,
   author = "Lenka Hol\'{i}kov\'{a} and Luk\'{a}\v{s} Hol\'{i}k and Ond\v{r}ej Leng\'{a}l and Olli Saarikivi and Margus Veanes and Tom\'{a}\v{s} Vojnar",
   title = "Regex Matching with Counting-Set Automata",
   pages = "1--30",
   journal = "Proceedings of the ACM on Programming Languages",
   volume = 4,
   number = 11,
   year = 2020,
   ISSN = "2475-1421",
   doi = "10.1145/3428286",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12388"
}
Back to top