Christoph Matheja

Christoph Matheja

Auto-generated profile, based on publicly available information

Christoph Matheja

Technical University of Denmark

Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
29 August 2018 in Journal of the ACM
Verified
Journal Article
Open access
BKBenjamin Lucien Kaminski
Benjamin Lucien Kaminski
JKJoost-Pieter Katoen
Joost-Pieter Katoen
CMChristoph Matheja
Christoph Matheja
FOFederico Olmedo
Federico Olmedo
This article presents a wp--style calculus for obtaining bounds on the expected runtime of randomized algorithms. Its application includes determining the (possibly infinite) expected termination time of a randomized algorithm and proving positive almost--sure termination—does a program terminate with probability one in finite expected time? We provide several proof rules for bounding the runtime of loops, and prove the soundness of the approach with respect to a simple operational model. We show that our approach is a conservative extension of Nielson’s approach for reasoning about the runtime of deterministic programs. We analyze the expected runtime of some example programs including the coupon collector’s problem, a one--dimensional random walk and a randomized binary search.

1 January 2016
Verified
Book Chapter
Closed access
PDF file
BKBenjamin Lucien Kaminski
Benjamin Lucien Kaminski
JKJoost-Pieter Katoen
Joost-Pieter Katoen
CMChristoph Matheja
Christoph Matheja
FOFederico Olmedo
Federico Olmedo

5 July 2016
Verified
Conference Paper
Open access
PDF file
FOFederico Olmedo
Federico Olmedo
BKBenjamin Lucien Kaminski
Benjamin Lucien Kaminski
JKJoost-Pieter Katoen
Joost-Pieter Katoen
CMChristoph Matheja
Christoph Matheja
This paper presents a wp--style calculus for obtaining expectations on the outcomes of (mutually) recursive probabilistic programs. We provide several proof rules to derive one-- and two--sided bounds for such expectations, and show the soundness of our wp--calculus with respect to a probabilistic pushdown automaton semantics. We also give a wp--style calculus for obtaining bounds on the expected runtime of recursive programs that can be used to determine the (possibly infinite) time until termination of such programs.

2 January 2019 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
PDF file
KBKevin Batz
Kevin Batz
BKBenjamin Lucien Kaminski
Benjamin Lucien Kaminski
JKJoost-Pieter Katoen
Joost-Pieter Katoen
CMChristoph Matheja
Christoph Matheja
TNThomas Noll
Thomas Noll
We present quantitative separation logic (QSL). In contrast to classical separation logic, QSL employs quantities which evaluate to real numbers instead of predicates which evaluate to Boolean values. The connectives of classical separation logic, separating conjunction and separating implication, are lifted from predicates to quantities. This extension is conservative: Both connectives are backward compatible to their classical analogs and obey the same laws, e.g. modus ponens, adjointness, etc. Furthermore, we develop a weakest precondition calculus for quantitative reasoning about probabilistic pointer programs in QSL. This calculus is a conservative extension of both Ishtiaq’s, O’Hearn’s and Reynolds’ separation logic for heap-manipulating programs and Kozen’s / McIver and Morgan’s weakest preexpectations for probabilistic programs. Soundness is proven with respect to an operational semantics based on Markov decision processes. Our calculus preserves O’Hearn’s frame rule , which enables local reasoning. We demonstrate that our calculus enables reasoning about quantities such as the probability of terminating with an empty heap, the probability of reaching a certain array permutation, or the expected length of a list.

15 May 2018 in Acta Informatica
Verified
Journal Article
Closed access
PDF file
BKBenjamin Lucien Kaminski
Benjamin Lucien Kaminski
JKJoost-Pieter Katoen
Joost-Pieter Katoen
CMChristoph Matheja
Christoph Matheja

20 April 2023
Verified
Book Chapter
Open access
PDF file
KBKevin Batz
Kevin Batz
MCMingshuai Chen
Mingshuai Chen
SJSebastian Junges
Sebastian Junges
BKBenjamin Lucien Kaminski
Benjamin Lucien Kaminski
JKJoost-Pieter Katoen
Joost-Pieter Katoen
CMChristoph Matheja
Christoph Matheja
Essential tasks for the verification of probabilistic programs include bounding expected outcomes and proving termination in finite expected runtime. We contribute a simple yet effective inductive synthesis approach for proving such quantitative reachability properties by generating inductive invariants on source-code level. Our implementation shows promise: It finds invariants for (in)finite-state programs, can beat state-of-the-art probabilistic model checkers, and is competitive with modern tools dedicated to invariant synthesis and expected runtime reasoning.