Fast Matching of Regular Patterns with Synchronizing Counting

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F23%3APU149396" target="_blank" >RIV/00216305:26230/23:PU149396 - isvavai.cz</a>

Result on the web

<a href="https://link.springer.com/chapter/10.1007/978-3-031-30829-1_19" target="_blank" >https://link.springer.com/chapter/10.1007/978-3-031-30829-1_19</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-30829-1_19" target="_blank" >10.1007/978-3-031-30829-1_19</a>

Result language

angličtina

Original language name

Fast Matching of Regular Patterns with Synchronizing Counting

Original language description

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

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Foundations of Software Science and Computation Structures

ISBN

—

ISSN

0302-9743

e-ISSN

—

Number of pages

21

Pages from-to

392-412

Publisher name

Springer Verlag

Place of publication

Heidelberg

Event location

Paris

Event date

Apr 22, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—