5 papers
Algorithms and fine-grained complexity for nondeterministic and symmetric difference automata
Dmitry Chistikov, RadosÅaw Piórkowski, Neha Rino +1
Symmetric difference automata (XNFA) are a variant of standard finite automata in which an input word is accepted iff the number of accepting runs is odd. Equivalently, these are w…
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…
Investigating the Role of Prompting and External Tools in Hallucination Rates of Large Language Models
Liam Barkley, Brink van der Merwe
Large Language Models (LLMs) are powerful computational models trained on extensive corpora of human-readable text, enabling them to perform general-purpose language understanding…