Detail výsledku

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. no. 1, p. 392-412. ISSN: 0302-9743.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Holík Lukáš, doc. Mgr., Ph.D., UITS (FIT)
Síč Juraj, Mgr., UITS (FIT)
Holíková Lenka, Ing., Ph.D., UITS (FIT)
Vojnar Tomáš, prof. Ing., Ph.D., UITS (FIT)
Abstrakt

Fast matching of regular expressions with bounded repetition, aka counting, such as (){,}, i.e., matching linear in the length of the text and independent of the repetition bounds, has been an open problem for at least two decades. We show that, for a wide class of regular expressions with counting, which we call synchronizing, fast matching is possible. We empirically show that the class covers nearly all counting used in usual applications of regex matching. This complexity result is based on an improvement and analysis of a recent matching algorithm that compiles regexes to deterministic counting-set automata (automata with registers that hold sets of numbers).

Klíčová slova

regex, counting automata, synchronizing counting

URL
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
Konference
European Joint Conferences on Theory and Practice of Software -- ETAPS'23
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
Projekty
Efektivní konečné automaty pro automatické usuzování, MŠMT, ERC CZ, LL1908, zahájení: 2020-01-01, ukončení: 2024-12-31, ukončen
Pokročilá analýza a verifikace pro pokročilý software, GAČR, Standardní projekty, GA23-06506S, zahájení: 2023-01-01, ukončení: 2025-12-31, řešení
Reliable, Secure, and Intelligent Computer Systems, VUT, Vnitřní projekty VUT, FIT-S-23-8151, zahájení: 2023-03-01, ukončení: 2026-02-28, řešení
Výzkumné skupiny
Automata@FIT (VZ Automata@FIT)
Výzkumná skupina automatizované analýzy a verifikace - VeriFIT (VZ VERIFIT)
Pracoviště
Ústav inteligentních systémů (UITS)
Nahoru