Metraipolis › archive › dc_da1f7acda869
Certification of Bilateral Patience Sort in Theorema and Rocq — arXiv:2609.34889
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.34889
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T00:42:59.459Z
- SHA-256 of the archived text
d0086690e0093f07ff2437d19e8aa44426594dc0fd3fd454b758ae5cbdf9b9b8- Stable URL of this page
https://metraipolis.com/documento/dc_da1f7acda869
How to cite
Certification of Bilateral Patience Sort in Theorema and Rocq — arXiv:2609.34889 — arXiv (en), https://arxiv.org/abs/2609.34889 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_da1f7acda869 (Metraipolis archive dc_da1f7acda869, sha256 d0086690e0093f07ff2437d19e8aa44426594dc0fd3fd454b758ae5cbdf9b9b8)
BibTeX
@misc{dcda1f7acda869,
title = {Certification of Bilateral Patience Sort in Theorema and Rocq — arXiv:2609.34889},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.34889},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_da1f7acda869; sha256 d0086690e0093f07ff2437d19e8aa44426594dc0fd3fd454b758ae5cbdf9b9b8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34889. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
This is a case study on a specific version of the Patience Sort algorithm in which we illustrate the evolution of it from an intuitive but inefficient nested recursion into a more complex but more efficient tail recursion, together with its formal implementation and certification in Theorema and Rocq (formerly Coq). We identify some general principles of algorithm transformation, and we develop the necessary background theory and proof methods. As a significant distinctive aspect, the approach in Theorema uses multisets, which simplifies the whole process and makes it more intuitive. The certification process reveals significant differences between the Theorema and Rocq approaches, about which we provide a comparative analysis with respect to algorithm definition, proof development, and proof effort. This analysis offers insights into how algorithm design influences the complexity and structure of formal proofs and demonstrates how non-trivial algorithms can be effectively verified across different formal frameworks. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.LO). Categorie arXiv: Logic in Computer Science (cs.LO). Pagina del lavoro: https://arxiv.org/abs/2609.34889 — 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-08T00:17:09.500Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).