Florian Funke

Florian Funke

Auto-generated profile, based on publicly available information

Florian Funke

Technische Universität Dresden

Research Focus & Metrics

Academic Career Length

7Years (2020-Present)

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

Representative Publications

View All Publications
17 April 2020
Verified
Book Chapter
Open access
PDF file
FFFlorian Funke
Florian Funke
SJSimon Jantsch
Simon Jantsch
CBChristel Baier
Christel Baier
This paper introduces Farkas certificates for lower and upper bounds on minimal and maximal reachability probabilities in Markov decision processes (MDP), which we derive using an MDP-variant of Farkas’ Lemma. The set of all such certificates is shown to form a polytope whose points correspond to witnessing subsystems of the model and the property. Using this correspondence we can translate the problem of finding minimal witnesses to the problem of finding vertices with a maximal number of zeros. While computing such vertices is computationally hard in general, we derive new heuristics from our formulations that exhibit competitive performance compared to state-of-the-art techniques. As an argument that asymptotically better algorithms cannot be hoped for, we show that the decision version of finding minimal witnesses is \({\text {NP}}\)-complete even for acyclic Markov chains.

15 July 2021
Verified
Book Chapter
Open access
PDF file
CBChristel Baier
Christel Baier
NCNorine Coenen
Norine Coenen
BFBernd Finkbeiner
Bernd Finkbeiner
FFFlorian Funke
Florian Funke
SJSimon Jantsch
Simon Jantsch
JSJulian Siber
Julian Siber
We present a causality-based algorithm for solving two-player reachability games represented by logical constraints. These games are a useful formalism to model a wide array of problems arising, e.g., in program synthesis. Our technique for solving these games is based on the notion of subgoals, which are slices of the game that the reachability player necessarily needs to pass through in order to reach the goal. We use Craig interpolation to identify these necessary sets of moves and recursively slice the game along these subgoals. Our approach allows us to infer winning strategies that are structured along the subgoals. If the game is won by the reachability player, this is a strategy that progresses through the subgoals towards the final goal; if the game is won by the safety player, it is a permissive strategy that completely avoids a single subgoal. We evaluate our prototype implementation on a range of different games. On multiple benchmark families, our prototype scales dramatically better than previously available tools.

25 April 2022 in Innovations in Systems and Software Engineering
Verified
Journal Article
Open access
PDF file
RZRobin Ziemek
Robin Ziemek
JPJakob Piribauer
Jakob Piribauer
FFFlorian Funke
Florian Funke
SJSimon Jantsch
Simon Jantsch
CBChristel Baier
Christel Baier
By combining two of the central paradigms of causality, namely counterfactual reasoning and probability-raising, we introduce a probabilistic notion of cause in Markov chains. Such a cause consists of finite executions of the probabilistic system after which the probability of an $$\omega $$ ω -regular effect exceeds a given threshold. The cause, as a set of executions, then has to cover all behaviors exhibiting the effect. With these properties, such causes can be used for monitoring purposes where the aim is to detect faulty behavior before it actually occurs. In order to choose which cause should be computed, we introduce multiple types of costs to capture the consumption of resources by the system or monitor from different perspectives, and study the complexity of computing cost-minimal causes.

29 March 2022
Verified
Book Chapter
Open access
PDF file
CBChristel Baier
Christel Baier
FFFlorian Funke
Florian Funke
JPJakob Piribauer
Jakob Piribauer
RZRobin Ziemek
Robin Ziemek
The purpose of this paper is to introduce a notion of causality in Markov decision processes based on the probability-raising principle and to analyze its algorithmic properties. The latter includes algorithms for checking cause-effect relationships and the existence of probability-raising causes for given effect scenarios. Inspired by concepts of statistical analysis, we study quality measures (recall, coverage ratio and f-score) for causes and develop algorithms for their computation. Finally, the computational complexity for finding optimal causes with respect to these measures is analyzed.

12 October 2020
Verified
Book Chapter
Closed access
PDF file
SJSimon Jantsch
Simon Jantsch
FFFlorian Funke
Florian Funke
CBChristel Baier
Christel Baier

7 September 2022
Verified
Book Chapter
Closed access
PDF file
CBChristel Baier
Christel Baier
CDClemens Dubslaff
Clemens Dubslaff
FFFlorian Funke
Florian Funke
SJSimon Jantsch
Simon Jantsch
JPJakob Piribauer
Jakob Piribauer
RZRobin Ziemek
Robin Ziemek