Detail publikace

Fast Matching of Regular Patterns with Synchronizing Counting

HOLÍK, L.; HOLÍKOVÁ, L.; SÍČ, J.; VOJNAR, T. Fast Matching of Regular Patterns with Synchronizing Counting. In Foundations of Software Science and Computation Structures. Lecture Notes in Computer Science. Heidelberg: Springer Verlag, 2023. p. 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
anglicky
Autoři
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Síč Juraj, Mgr. (UITS)
Holíková Lenka, Ing., Ph.D. (UITS)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS)
URL
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, roč. 13992, č. 1, ISSN 0302-9743
Sborník
Foundations of Software Science and Computation Structures
Vydavatel
Springer Verlag
Místo
Heidelberg
DOI
10.1007/978-3-031-30829-1_19
EID Scopus
2-s2.0-85161369927
BibTeX 
@inproceedings{BUT185169,
  author="Lukáš {Holík} and Juraj {Síč} and Lenka {Holíková} and Tomáš {Vojnar}",
  title="Fast Matching of Regular Patterns with Synchronizing Counting",
  booktitle="Foundations of Software Science and Computation Structures",
  year="2023",
  journal="Lecture Notes in Computer Science",
  volume="13992",
  number="1",
  pages="392--412",
  publisher="Springer Verlag",
  address="Heidelberg",
  doi="10.1007/978-3-031-30829-1\{_}19",
  issn="0302-9743",
  url="https://link.springer.com/chapter/10.1007/978-3-031-30829-1_19"
}
Soubory
Nahoru