Joachim Klein
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Joachim Klein has a total of 60 co-authors. Here are the top co-authors by number of shared publications:
- Sascha Klüppelholz
Technische Universität Dresden
25 shared publications Christel Baier
Technische Universität Dresden
23 shared publications- Christel Baier
Technische Universität Dresden
10 shared publications Marcus Daum
Technische Universität Dresden
7 shared publicationsSteffen Märcker
Technische Universität Dresden
7 shared publicationsClemens Dubslaff
Technische Universität Dresden
6 shared publications
Latest Publications
- Open Access
- 1 October 2021
- Published by Springer Nature in Formal Methods in System Design
- Vol. 58 (1-2) , 42-82
From LTL to unambiguous Büchi automata via disambiguation of alternating automata
Due to the high complexity of translating linear temporal logic (LTL) to deterministic automata, several forms of “restricted” nondeterminism have been considered with the aim of maintaining some of the benefits of deterministic automata, while at the same time allowing more efficient translations from LTL. One of them is the notion of unambiguity. This paper proposes a new algorithm for the generation of unambiguous Büchi automata (UBA) from LTL formulas. Unlike other approaches it is based on a known translation from very weak alternating automata (VWAA) to NBA. A notion of unambiguity for alternating automata is introduced and it is shown that the VWAA-to-NBA translation preserves unambiguity. Checking unambiguity of VWAA is determined to be PSPACE-complete, both for the explicit and symbolic encodings of alternating automata. The core of the LTL-to-UBA translation is an iterative disambiguation procedure for VWAA. Several heuristics are introduced for different stages of the procedure. We report on an implementation of our approach in the tool and compare it to an existing LTL-to-UBA implementation in the tool set. Our experiments cover model checking of Markov chains, which is an important application of UBA.
- 1 October 2021
- Published by Springer Nature in Formal Methods in System Design
- Vol. 58 (1-2) , 42-82
Open AccessFrom LTL to unambiguous Büchi automata via disambiguation of alternating automata
Due to the high complexity of translating linear temporal logic (LTL) to deterministic automata, several forms of “restricted” nondeterminism have been considered with the aim of maintaining some of the benefits of deterministic automata, while at the same time allowing more efficient translations from LTL. One of them is the notion of unambiguity. This paper proposes a new algorithm for the generation of unambiguous Büchi automata (UBA) from LTL formulas. Unlike other approaches it is based on a known translation from very weak alternating automata (VWAA) to NBA. A notion of unambiguity for alternating automata is introduced and it is shown that the VWAA-to-NBA translation preserves unambiguity. Checking unambiguity of VWAA is determined to be PSPACE-complete, both for the explicit and symbolic encodings of alternating automata. The core of the LTL-to-UBA translation is an iterative disambiguation procedure for VWAA. Several heuristics are introduced for different stages of the procedure. We report on an implementation of our approach in the tool and compare it to an existing LTL-to-UBA implementation in the tool set. Our experiments cover model checking of Markov chains, which is an important application of UBA.
- 23 September 2019
- Published by Springer Nature
- p. 262-279
From LTL to Unambiguous Büchi Automata via Disambiguation of Alternating Automata
- 23 September 2019
- Published by Springer Nature
- p. 262-279
From LTL to Unambiguous Büchi Automata via Disambiguation of Alternating Automata
- Open Access
- 4 April 2019
- Published by Springer Nature
- p. 69-92
The 2019 Comparison of Tools for the Analysis of Quantitative Formal Models
- 4 April 2019
- Published by Springer Nature
- p. 69-92
Open AccessThe 2019 Comparison of Tools for the Analysis of Quantitative Formal Models
- 7 April 2018
- Published by Springer Nature
- p. 38-56
Energy-Utility Analysis of Probabilistic Systems with Exogenous Coordination
- 7 April 2018
- Published by Springer Nature
- p. 38-56
Energy-Utility Analysis of Probabilistic Systems with Exogenous Coordination
- Open Access
- 6 September 2017
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 256, 16-30
Parametric Markov Chains: PCTL Complexity and Fraction-free Gaussian Elimination
Parametric Markov chains have been introduced as a model for families of stochastic systems that rely on the same graph structure, but differ in the concrete transition probabilities. The latter are specified by polynomial constraints for the parameters. Among the tasks typically addressed in the analysis of parametric Markov chains are (1) the computation of closed-form solutions for reachabilty probabilities and other quantitative measures and (2) finding symbolic representations of the set of parameter valuations for which a given temporal logical formula holds as well as (3) the decision variant of (2) that asks whether there exists a parameter valuation where a temporal logical formula holds. Our contribution to (1) is to show that existing implementations for computing rational functions for reachability probabilities or expected costs in parametric Markov chains can be improved by using fraction-free Gaussian elimination, a long-known technique for linear equation systems with parametric coefficients. Our contribution to (2) and (3) is a complexity-theoretic discussion of the model checking problem for parametric Markov chains and probabilistic computation tree logic (PCTL) formulas. We present an exponential-time algorithm for (2) and a PSPACE upper bound for (3). Moreover, we identify fragments of PCTL and subclasses of parametric Markov chains where (1) and (3) are solvable in polynomial time and establish NP-hardness for other PCTL fragments.Comment: In Proceedings GandALF 2017, arXiv:1709.0176
- 6 September 2017
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 256, 16-30
Open AccessParametric Markov Chains: PCTL Complexity and Fraction-free Gaussian Elimination
Parametric Markov chains have been introduced as a model for families of stochastic systems that rely on the same graph structure, but differ in the concrete transition probabilities. The latter are specified by polynomial constraints for the parameters. Among the tasks typically addressed in the analysis of parametric Markov chains are (1) the computation of closed-form solutions for reachabilty probabilities and other quantitative measures and (2) finding symbolic representations of the set of parameter valuations for which a given temporal logical formula holds as well as (3) the decision variant of (2) that asks whether there exists a parameter valuation where a temporal logical formula holds. Our contribution to (1) is to show that existing implementations for computing rational functions for reachability probabilities or expected costs in parametric Markov chains can be improved by using fraction-free Gaussian elimination, a long-known technique for linear equation systems with parametric coefficients. Our contribution to (2) and (3) is a complexity-theoretic discussion of the model checking problem for parametric Markov chains and probabilistic computation tree logic (PCTL) formulas. We present an exponential-time algorithm for (2) and a PSPACE upper bound for (3). Moreover, we identify fragments of PCTL and subclasses of parametric Markov chains where (1) and (3) are solvable in polynomial time and establish NP-hardness for other PCTL fragments.Comment: In Proceedings GandALF 2017, arXiv:1709.0176
- 13 August 2017
- Published by Springer Nature
- p. 349-366
Computing Conditional Probabilities: Implementation and Evaluation
- 13 August 2017
- Published by Springer Nature
- p. 349-366
Computing Conditional Probabilities: Implementation and Evaluation
- 13 July 2017
- Published by Springer Nature
- p. 160-180
Ensuring the Reliability of Your Model Checker: Interval Iteration for Markov Decision Processes
- 13 July 2017
- Published by Springer Nature
- p. 160-180
Ensuring the Reliability of Your Model Checker: Interval Iteration for Markov Decision Processes
- 31 March 2017
- Published by Springer Nature
- p. 269-285
Maximizing the Conditional Expected Reward for Reaching the Goal
- 31 March 2017
- Published by Springer Nature
- p. 269-285
Maximizing the Conditional Expected Reward for Reaching the Goal