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

• Applying data refinement for monadic programs to Hopcroft's algorithm
• scientific article; zbMATH DE number 7649969 (Why is no real title available?)
• 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

(7)

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

Describes a project that uses

Uses Software

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

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)