Erweiterte Verifikationskalküle für Probabilistische Programme

Abstract

Ich habe mich mit der quantitativen Analyse probabilistischer Programme beschäftigt und dabei vornehmlich zwei Aspekte untersucht: Die Analysetechniken selbst sowie die Komplexität der Analyseprobleme. Bezüglich Analysetechniken gibt meine Dissertation zunächst eine Einführung in den Kalkül der schwächsten Vorerwartungen à la McIver&Morgan. Es folgen selbst entwickelte, erweiterte Kalküle zur Analyse erwarteter Laufzeiten, bedingter Erwartungswerte und der Erwartungswerte vorzeichenbehafteter Zufallsvariablen. Bezüglich der Komplexität der Analyse probabilistischer Programme - unabhängig von der verwendeten Analysetechnik - habe ich die Approximation von Erwartungswerten und Kovarianzen, die Entscheidbarkeit der Terminierung probabilistischer Programme und die Sinnhaftigkeit unterschiedlicher probabilistischer Terminierungsbegriffe untersucht.