Detail publikace

Regex Matching with Counting-Set Automata

HOLÍKOVÁ Lenka, HOLÍK Lukáš, LENGÁL Ondřej, SAARIKIVI Olli, VEANES Margus a VOJNAR Tomáš. Regex Matching with Counting-Set Automata. Proceedings of the ACM on Programming Languages, roč. 4, č. 11, 2020, s. 1-30. ISSN 2475-1421. Dostupné z: https://www.microsoft.com/en-us/research/uploads/prod/2020/09/MSR-TR-2020-31.pdf
Název česky
Hledání regulárních výrazů za pomocí automatů s čítačovými registry
Typ
článek v časopise
Jazyk
angličtina
Autoři
Holíková Lenka, Ing. (UITS FIT VUT)
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT)
Lengál Ondřej, Ing., Ph.D. (UITS FIT VUT)
Saarikivi Olli (MSR)
Veanes Margus (MSR)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT)
URL
Klíčová slova

porovnávání regulárních výrazů, omezení opakování, ReDoS, determinizace, Antimiovy derivativy, čítačové automaty, automaty s čítačovými registry

Abstrakt

Navrhli jsme řešení problému efektivního porovnávání regulárních výrazů s omezeným počtem opakování, například (ab) {1,100}, s použitím deterministických automatů. Za tímto účelem jsme představili automaty s čítačovými registry, automaty s registry pro ukládání množin celých čísel, nad kterými lze provádět operace v konstantním čase. Představili jsme algoritmus, který převede velkou podtřídu regulární výrazy na deterministické automaty s čítačovými registry. Konkrétněji (1) nový překlad regulární výrazů s čítači na čítačové automaty, nedeterministické automaty s omezenými čítači, a 2) determinizace čítačových automatů na automaty s čítačovými registry. Hlavní výhodou algoritmu je, že velikost vytvořených automatů s čítačovými registry nezávisí na hodnotě omezení čítačů v regulárních výrazech (zatímco velikost deterministických čítačů je na nich závislá exponenciálně). Naše experimentální výsledky potvrdily, že deterministické automaty s čítačovými registry vytvořené pro regulární výrazy s čítači z praxe jsou skutečně mnohem menší než odpovídající deterministické čítačové automaty. A především, že náš prototyp nástroje pro porovnávání regulárních výrazů zvládá i praktické regulární výrazy s opakováním nezávisle na hodnotě omezení čítačů. Zvládne regulární výrazy s čítači, se kterými mají ostatní obdobné nástroje problém.

Rok
2020
Strany
1-30
Časopis
Proceedings of the ACM on Programming Languages, roč. 4, č. 11, ISSN 2475-1421
Vydavatel
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"
}
Nahoru