Detail publikačního výsledku

Fast Matching of Regular Patterns with Synchronizing Counting

HOLÍK, L.; HOLÍKOVÁ, L.; SÍČ, J.; VOJNAR, T.

Originální název

Fast Matching of Regular Patterns with Synchronizing Counting

Anglický název

Fast Matching of Regular Patterns with Synchronizing Counting

Druh

Stať ve sborníku v databázi WoS či Scopus

Originální 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).

Anglický 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

Klíčová slova v angličtině

regex, counting automata, synchronizing counting

Autoři

HOLÍK, L.; HOLÍKOVÁ, L.; SÍČ, J.; VOJNAR, T.

Rok RIV

2024

Vydáno

21.04.2023

Nakladatel

Springer Verlag

Místo

Heidelberg

Kniha

Foundations of Software Science and Computation Structures

ISSN

0302-9743

Periodikum

Lecture Notes in Computer Science

Svazek

13992

Číslo

1

Stát

Spolková republika Německo

Strany od

392

Strany do

412

Strany počet

21

URL

https://link.springer.com/chapter/10.1007/978-3-031-30829-1_19

Plný text v Digitální knihovně

http://hdl.handle.net/11012/244327

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"
}