Metraipolis › archive › dc_9eff191113ea
Certified Split Windows for Parallel Lexing: Recovering Boundaries Where No Byte Certifies — arXiv:2608.09761
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.09761
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T08:52:52.965Z
- SHA-256 of the archived text
9cc1168bdbdd60dfb8e678630f4f84809b0bd2cd5179ba570fa6dc4dc14681b7- Stable URL of this page
https://metraipolis.com/documento/dc_9eff191113ea
How to cite
Certified Split Windows for Parallel Lexing: Recovering Boundaries Where No Byte Certifies — arXiv:2608.09761 — arXiv (en), https://arxiv.org/abs/2608.09761 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9eff191113ea (Metraipolis archive dc_9eff191113ea, sha256 9cc1168bdbdd60dfb8e678630f4f84809b0bd2cd5179ba570fa6dc4dc14681b7)
BibTeX
@misc{dc9eff191113ea,
title = {Certified Split Windows for Parallel Lexing: Recovering Boundaries Where No Byte Certifies — arXiv:2608.09761},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.09761},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9eff191113ea; sha256 9cc1168bdbdd60dfb8e678630f4f84809b0bd2cd5179ba570fa6dc4dc14681b7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.09761. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 predecessor's controlled study certify no byte once string, comment, or whitespace-run forms are included ( arXiv:2608.03473 ). We generalize from a byte to a bounded window: a byte string after which the position where the current token began is known, regardless of surrounding context. We certify the directly usable form of that recovery: the token covering the window's final byte begins at the reported origin. The certificate is conditional on occurrence and may be vacuous; every applicability figure counts only windows carrying an asserted completely tokenizable occurrence witness. We give a conservative model of a maximal-munch scanner's possible histories across a window, prove it sound, and decide reachability in that model exactly by exhausting a finite quotient of its reachable configurations, so every answer of the unbudgeted procedure is either a certified window with its origin or a proof that the model admits none. Within the stated flat, completely-tokenizable scope, model-positive answers are semantic certificates; negatives are relative to the conservative model, which deliberately refuses some windows a greedy scanner would allow. A token set in which some token matches the empty string is decided through its positive-width equivalent, the same automaton entered through a start state that does not accept, which changes no scan. In a sample of 400 random token sets, 322 of the 337 sets certifying no byte gain a witnessed window, with zero inconclusive searches, and every exact-empty row of the predecessor's study gains a witnessed window of two to four bytes. The analysis runs once after automaton construction, using only the compiled tables and no input. Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-08-11 in cs.DC). Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Distributed, Parallel, and Cluster Computing (cs.DC); Programming Languages (cs.PL). Pagina del lavoro: https://arxiv.org/abs/2608.09761 — 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-19T08:50:23.793Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).