Detail publikace

Fast Matching of Regular Patterns with Synchronizing Counting

HOLÍK Lukáš, HOLÍKOVÁ Lenka, SÍČ Juraj a VOJNAR Tomáš. Fast Matching of Regular Patterns with Synchronizing Counting. In: Foundations of Software Science and Computation Structures. Heidelberg: Springer Verlag, 2023, s. 392-412. ISSN 0302-9743.
Název česky
Rychlé porovnávání regulárních vzorů se synchronizovaným počítáním
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT)
Holíková Lenka, Ing. (UITS FIT VUT)
Síč Juraj, Mgr. (UITS FIT VUT)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT)
Klíčová slova

regex, počítací automaty, synchronizované počítání

Abstrakt

Rychlé porovnávání regulárních výrazů s omezeným opakováním, tzv. počítání, jako je (){,}, tj. porovnávání lineární v délce textu a nezávislé na hranicích opakování, je otevřeným problémem již nejméně dvě desetiletí. Ukážeme, že pro širokou třídu regulárních výrazů s počítáním, které nazýváme synchronizované, je rychlé porovnávání možné. Empiricky ukazujeme, že tato třída pokrývá téměř všechna počítání používaná v obvyklých aplikacích porovnávání regexů. Tento výsledek složitosti je založen na vylepšení a analýze nedávného párovacího algoritmu, který sestavuje regexy do deterministických počítacích automatů (automaty s registry, které uchovávají množiny čísel).

Rok
2023
Strany
392-412
Časopis
Lecture Notes in Computer Science, č. 13992, ISSN 0302-9743
Sborník
Foundations of Software Science and Computation Structures
Konference
European Joint Conferences on Theory and Practice of Software -- ETAPS'23, Paris, FR
Vydavatel
Springer Verlag
Místo
Heidelberg, DE
DOI
10.1007/978-3-031-30829-1_19
EID Scopus
2-s2.0-85161369927
BibTeX 
@INPROCEEDINGS{FITPUB13002,
   author = "Luk\'{a}\v{s} Hol\'{i}k and Lenka Hol\'{i}kov\'{a} and Juraj S\'{i}\v{c} and Tom\'{a}\v{s} Vojnar",
   title = "Fast Matching of Regular Patterns with Synchronizing Counting",
   pages = "392--412",
   booktitle = "Foundations of Software Science and Computation Structures",
   journal = "Lecture Notes in Computer Science",
   number = 13992,
   year = 2023,
   location = "Heidelberg, DE",
   publisher = "Springer Verlag",
   ISSN = "0302-9743",
   doi = "10.1007/978-3-031-30829-1\_19",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/13002"
}
Nahoru