24 citations · 39 across the 5 of their papers we have counts for
5 papers
Efficient Regex Matching with Sparse Counting-Sets
Martin Berglund, Brink van der Merwe, Sicheol Sung
Regular expressions with counting operations (c-regexes) offer a compact representation of repeating patterns by allowing numerical bounds to be added to subexpressions. Recent wor…
Selective Memoization for Efficient Backtracking Regular Expression Matching
Martin Berglund, Brink van der Merwe, Iain le Roux
Backtracking regular expression matchers are widely used due to their expressive power but may exhibit exponential worst-case matching time. Memoization provides a principled metho…
Constructing a BPE Tokenization DFA
Martin Berglund, Willeke Martens, Brink van der Merwe
Many natural language processing systems operate over tokenizations of text to address the open-vocabulary problem. In this paper, we give and analyze an algorithm for the efficien…
Formalizing BPE Tokenization
Martin Berglund, Brink van der Merwe
In this paper, we formalize practical byte pair encoding tokenization as it is used in large language models and other NLP systems, in particular we formally define and investigate…
Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching
Martin Berglund, Frank Drewes, Brink van der Merwe
We develop a formal perspective on how regular expression matching works in Java, a popular representative of the category of regex-directed matching engines. In particular, we def…