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).