Publication result detail

Fast Matching of Regular Patterns with Synchronizing Counting

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

Original Title

Fast Matching of Regular Patterns with Synchronizing Counting

English Title

Fast Matching of Regular Patterns with Synchronizing Counting

Type

Paper in proceedings (conference paper)

Original Abstract

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).

English abstract

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).

Keywords

regex, counting automata, synchronizing counting

Key words in English

regex, counting automata, synchronizing counting

Authors

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

RIV year

2024

Released

21.04.2023

Publisher

Springer Verlag

Location

Heidelberg

Book

Foundations of Software Science and Computation Structures

ISBN

0302-9743

Periodical

Lecture Notes in Computer Science

Volume

13992

Number

1

State

Federal Republic of Germany

Pages from

392

Pages to

412

Pages count

21

URL

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

Full text in the Digital Library

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

Documents

978-3-031-30829-1_19