3 papers
cs.FL2026
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…
cs.FL2026
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…
cs.FL2025
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…