Séminaire - Tobias Nipkow : Verification of functional data structures: Correctness and complexity
Contenu de l'épisode
Xavier Leroy
Collège de France
Science du logiciel
Année 2022-2023
Structures de données persistantes
Séminaire - Tobias Nipkow : Verification of functional data structures: Correctness and complexity
The talk gives a brief overview of our book "Functional Algorithms, Verified!" and its approach to verifying not just correctness but also running time of a large collection of functional algorithms. Then, two examples are presented in more detail: real time queues and double-ended queues that are implemented purely functionally with the help of stacks and whose operations have guaranteed constant running time.