2 papers
cs.FL2026
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…
cs.FL2024
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…