A Calculus for Amortized Expected Runtimes

Batz, K; Kaminski, BL; Katoen, JP; Matheja, C; Verscht, L

Batz, K (通讯作者),Rhein Westfal TH Aachen, Aachen, Germany.

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL, 2023; 7 (POPL):

Abstract

We develop a weakest-precondition-style calculus a la Dijkstra for reasoning about amortized expected runtimes of randomized algorithms with access to......

Full Text Link