DiscoverSciences du logiciel - Xavier LeroySéminaire - Tobias Nipkow : Verification of functional data structures: Correctness and complexity
Séminaire - Tobias Nipkow : Verification of functional data structures: Correctness and complexity

Séminaire - Tobias Nipkow : Verification of functional data structures: Correctness and complexity

Update: 2023-03-23
Share

Description

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.

Comments 
In Channel
loading
00:00
00:00
x

0.5x

0.8x

1.0x

1.25x

1.5x

2.0x

3.0x

Sleep Timer

Off

End of Episode

5 Minutes

10 Minutes

15 Minutes

30 Minutes

45 Minutes

60 Minutes

120 Minutes

Séminaire - Tobias Nipkow : Verification of functional data structures: Correctness and complexity

Séminaire - Tobias Nipkow : Verification of functional data structures: Correctness and complexity

Xavier Leroy