EUVIMEDEUVIMED entdecken
Crossref

Efficient Regex Matching with Sparse Counting-Sets

Martin Berglund, Brink van der Merwe, Sicheol Sung

Electronic Proceedings in Theoretical Computer Science · 25.06.2026 · 446 · 19-36

DOI: 10.4204/eptcs.446.2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Electronic Proceedings in Theoretical Computer Science, online erschienen am 25.06.2026. Verfasst von Martin Berglund und 2 weiteren Autor:innen. Die Arbeit nennt 12 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Regular expressions with counting operations (c-regexes) offer a compact representation of repeating patterns by allowing numerical bounds to be added to subexpressions. Recent work introduced the counting-set data structure, which allows simultaneous updates of multiple counter values for efficient matching. However, this approach suffers from a performance bottleneck when counting-sets must be replicated due to the presence of branching transitions. We propose a sparse counting-set approach, which reduces the replication overhead by maintaining only essential counter values, thereby yielding a more efficient matching algorithm.

Zitieren

APA

Berglund, M., Merwe, B. V. D., & Sung, S. (2026). Efficient Regex Matching with Sparse Counting-Sets. Electronic Proceedings in Theoretical Computer Science, 446, 19-36. https://doi.org/10.4204/eptcs.446.2

Vancouver

Berglund M, Merwe BVD, Sung S. Efficient Regex Matching with Sparse Counting-Sets. Electronic Proceedings in Theoretical Computer Science. 2026;446:19-36. doi:10.4204/eptcs.446.2

BibTeX
@article{Berglund2026,
  author = {Berglund, Martin and Merwe, Brink van der and Sung, Sicheol},
  title = {Efficient Regex Matching with Sparse Counting-Sets},
  journal = {Electronic Proceedings in Theoretical Computer Science},
  year = {2026},
  volume = {446},
  pages = {19--36},
  doi = {10.4204/eptcs.446.2}
}
Kostenlos starten →