27 citations · 62 across the 16 of their papers we have counts for
3 papers · 2 filters
Non-polynomial Worst-Case Analysis of Recursive Programs
Krishnendu Chatterjee, Hongfei Fu, Amir Kafshdar Goharshady
We study the problem of developing efficient approaches for proving worst-case bounds of non-deterministic recursive programs. Ranking functions are sound and complete for proving…
Automated Recurrence Analysis for Almost-Linear Expected-Runtime Bounds
Krishnendu Chatterjee, Hongfei Fu, Aniket Murhekar
We consider the problem of developing automated techniques for solving recurrence relations to aid the expected-runtime analysis of programs. Several classical textbook algorithms…
Termination of Nondeterministic Recursive Probabilistic Programs
Krishnendu Chatterjee, Hongfei Fu
We study the termination problem for nondeterministic recursive probabilistic programs. First, we show that a ranking-supermartingales-based approach is both sound and complete for…