Efficient Verified Implementation of Introsort and Pdqsort

DOI10.1007/978-3-030-51054-1_18MaRDI QIDQ5049010zbMATH OpenOpenAlexFDO

Authors Peter Lammich

Publication date 9 November 2022

Published in Automated Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-51054-1_18

Mathematics Subject Classification ID

Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)

Cites work

• scientific article; zbMATH DE number 7649969 (Why is no real title available?)
• Applying data refinement for monadic programs to Hopcroft's algorithm
• Introduction to algorithms.
• KeY: A Formal Method for Object-Oriented Systems
• Permission accounting in separation logic
• Proof of a recursive program: Quicksort
• Proving JDK's dual pivot quicksort correct
• Refinement to Imperative/HOL

Cited in

(5)

• Functional correctness of C implementations of Dijkstra's, Kruskal's, and Prim's algorithms
• For a few dollars more. Verified fine-grained algorithm analysis down to LLVM
• Refinement of parallel algorithms down to LLVM: applied to practically efficient parallel sorting
• A Machine-Checked Proof of the Average-Case Complexity of Quicksort in Coq
• Proving Quicksort Correct in Event-B

Describes a project that uses

Uses Software

• heapsort
• Archive Formal Proofs
• Rust
• Quicksort
• Boost
• Boost C++ Libraries

This page was built for publication: Efficient Verified Implementation of Introsort and Pdqsort

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5049010)