Metraipolis › archive › dc_58e2aed99f12

Finitely Verifiable Segmentation: Decidability for Every Tokenizer with a Finite-State Verifier — arXiv:2610.30168

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.30168
License (as archived)
CC0-1.0
Archived
2026-10-23T15:21:12.129Z
SHA-256 of the archived text
e8f7ae8ecdc241437c8a3dd3089298229d559532f2568064f94299b1b282aefc
Stable URL of this page
https://metraipolis.com/documento/dc_58e2aed99f12

How to cite

Finitely Verifiable Segmentation: Decidability for Every Tokenizer with a Finite-State Verifier — arXiv:2610.30168 — arXiv (en), https://arxiv.org/abs/2610.30168 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_58e2aed99f12 (Metraipolis archive dc_58e2aed99f12, sha256 e8f7ae8ecdc241437c8a3dd3089298229d559532f2568064f94299b1b282aefc)
BibTeX
@misc{dc58e2aed99f12,
  title = {Finitely Verifiable Segmentation: Decidability for Every Tokenizer with a Finite-State Verifier — arXiv:2610.30168},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.30168},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_58e2aed99f12; sha256 e8f7ae8ecdc241437c8a3dd3089298229d559532f2568064f94299b1b282aefc},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.30168. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. The first refines the synchronizing cut of code theory, and two more ask whether a certified cut, or the cuts of an inventory, let each piece scan alone. The class sits strictly between the online-scannable policies and those with regular domains, and its inner frontier is Choffrut's and decidable in polynomial time. Markings are length-preserving, so the class is exactly the rational segmentation policies, a normal form rather than a restriction, and what the decisions need is a supplied verifier. The class is closed under the operations pipelines use: composition over a labeled stage, restriction, splitting, and byte-fallback union of literal policies. Each composite inherits the six decisions, and certificates transfer between stages under four laws. Under rational, unifilar, almost surely stopping finite-state sources, each mass of the weighted section is an exact rational, and so is each rate where expected length is positive. Maximal-munch lexing, canonical byte-pair encoding and two-mode WordPiece instantiate the interface, and the munch library implements all six decisions. Every theorem carries an executable check, and every reported statistic is a program's own output.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.CL, nuovi lavori del giorno).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Computation and Language (cs.CL); Programming Languages (cs.PL).
Pagina del lavoro: https://arxiv.org/abs/2610.30168 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-23T15:09:38.376Z dalla pagina https://arxiv.org/list/cs.CL/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).