Inferring Expected Runtimes of Probabilistic Integer Programs Using Expected Sizes

We present a novel modular approach to infer upper bounds on the expected runtimes of probabilistic integer programs automatically. To this end, it computes bounds on the runtimes of program parts and on the sizes of their variables in an alternating way. To evaluate its power, we implemented our ap...

Descripción completa

Detalles Bibliográficos
Autores principales: Meyer, Fabian, Hark, Marcel, Giesl, Jürgen
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2021
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7979164/
http://dx.doi.org/10.1007/978-3-030-72016-2_14
Descripción
Sumario:We present a novel modular approach to infer upper bounds on the expected runtimes of probabilistic integer programs automatically. To this end, it computes bounds on the runtimes of program parts and on the sizes of their variables in an alternating way. To evaluate its power, we implemented our approach in a new version of our open-source tool KoAT.

Ejemplares similares