4 papers · 1 filter
Finitely Verifiable Segmentation: Decidability for Every Tokenizer with a Finite-State Verifier
Nicklas Nidhögg
A segmentation policy assigns to each byte string at most one segmentation into tokens. Call it finitely verifiable when a finite automaton over marked strings, bytes paired with b…
Certified Splitting: Decidability and Anchor Supply for Maximal-Munch Tokenization
Nicklas Nidhögg
A certificate is a window of bytes with an origin inside it: wherever the window occurs in a completely tokenizable input, the token covering the window's final byte begins at that…
Certified Split Points for Parallel Lexing: Exact and Modulo Discarded Tokens
Nicklas Nidhögg
Table-driven DFA lexing is sequential, since each transition depends on the previous byte's state. Scanning one input in parallel needs each chunk's entry state, which existing met…
Certified Split Windows for Parallel Lexing: Recovering Boundaries Where No Byte Certifies
Nicklas Nidhögg
A certified split point lets a parallel lexer cut unlexed input at a single byte with the serial token stream provably preserved, but several conventional token sets in the predece…