Metraipolis › archive › dc_be572db8a259
Order Maintenance in Worst-Case Constant Time, Verified — arXiv:2610.38616
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.38616
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:47:49.808Z
- SHA-256 of the archived text
d158e1aa77467ff3d1f7e878875d867a523ee7e40807f83bc87f025573e24da9- Stable URL of this page
https://metraipolis.com/documento/dc_be572db8a259
How to cite
Order Maintenance in Worst-Case Constant Time, Verified — arXiv:2610.38616 — arXiv (en), https://arxiv.org/abs/2610.38616 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_be572db8a259 (Metraipolis archive dc_be572db8a259, sha256 d158e1aa77467ff3d1f7e878875d867a523ee7e40807f83bc87f025573e24da9)
BibTeX
@misc{dcbe572db8a259,
title = {Order Maintenance in Worst-Case Constant Time, Verified — arXiv:2610.38616},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.38616},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_be572db8a259; sha256 d158e1aa77467ff3d1f7e878875d867a523ee7e40807f83bc87f025573e24da9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38616. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Order maintenance asks for a data structure that keeps a sequence of elements under insertions and deletions and tells which of two elements comes first. We give an algorithm, assembled from published components, that performs each operation in worst-case constant time, and verify it in Lean 4. The algorithm is a program for a random-access machine deeply embedded in Lean, whose interpreter counts every instruction. We prove that the program answers every query as a simple reference specification does, that each operation takes at most a fixed number of steps, independent of the number of elements and of the history, and that after $t$ operations no value it has computed has more than $O(\log t)$ bits, so it runs unchanged on a machine with words of that size. A verified translation that preserves step counts exactly connects the high-level proofs to the machine program, so the interpreter is the only cost model to trust. An unverified native implementation shows the algorithm's practical cost. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno). Categorie arXiv: Logic in Computer Science (cs.LO) ; Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2610.38616 — 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-11-01T02:17:58.613Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).