Detail publikace

Regex Matching with Counting-Set Automata

HOLÍKOVÁ, L.; HOLÍK, L.; LENGÁL, O.; SAARIKIVI, O.; VEANES, M.; VOJNAR, T. Regex Matching with Counting-Set Automata. Proceedings of the ACM on Programming Languages, 2020, vol. 4, no. 11, p. 1-30. ISSN: 2475-1421.
Název česky
Hledání regulárních výrazů za pomocí automatů s čítačovými registry
Typ
článek v časopise
Jazyk
anglicky
Autoři
Holíková Lenka, Ing., Ph.D. (UITS)
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Lengál Ondřej, Ing., Ph.D. (UITS)
SAARIKIVI, O.
Veanes Margus
Vojnar Tomáš, prof. Ing., Ph.D. (UITS)
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
DOI
10.1145/3428286
UT WoS
000685203900095
EID Scopus
2-s2.0-85097577301
BibTeX 
@article{BUT168498,
  author="HOLÍKOVÁ, L. and HOLÍK, L. and LENGÁL, O. and SAARIKIVI, O. and VEANES, M. and VOJNAR, T.",
  title="Regex Matching with Counting-Set Automata",
  journal="Proceedings of the ACM on Programming Languages",
  year="2020",
  volume="4",
  number="11",
  pages="1--30",
  doi="10.1145/3428286",
  issn="2475-1421",
  url="https://www.microsoft.com/en-us/research/uploads/prod/2020/09/MSR-TR-2020-31.pdf"
}
Nahoru