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. (VZ VERIFIT)
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}, spoužitím deterministických automatů. Za tímto účelem jsme představili automaty s čítačovýmiregistry, 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 jsmealgoritmus, který převede velkou podtřídu regulární výrazy na deterministické automatys čítačovými registry. Konkrétněji (1) nový překlad regulární výrazů s čítačina čí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 registrynezá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ýmiregistry vytvořené pro regulární výrazy s čítači z praxe jsouskuteč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ádneregulární výrazy s čítači, se kterými mají ostatní obdobné nástrojeproblé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