Finitely Verifiable Segmentation: Decidability for Every Tokenizer with a Finite-State Verifier
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 boundary bits, accepts exactly the policy's own segmentations. The automaton judges a proposed segmentation and need not compute one. The paper shows what that hypothesis buys. Four questions that practice settles by folklore become decidable, whether a window certifies a token boundary, whether the boundary gap is bounded, whether a mask keeps generation completable, and whether two policies are equivalent. The last three specialize limitedness, coaccessibility and the equivalence of single-valued transducers. T...
| Authors | Nicklas Nidhögg |
|---|---|
| Primary category | cs.FL |
| Published | 16 October 2026 |
| Last updated at source | 16 October 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 23 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.