Florian Frohn
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
Florian Frohn has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
- Jürgen Giesl
RWTH Aachen University
32 shared publications Thomas Ströder
Rhein Westfal TH Aachen, LuFG Informat 2, Aachen, Germany
10 shared publicationsJera Hensel
Rhein Westfal TH Aachen, LuFG Informat 2, Aachen, Germany
9 shared publicationsCarsten Fuhs
Department of Computer Science and Information Systems, Birkbeck, University of London, London, UK
6 shared publicationsCornelius Aschermann
RWTH Aachen University
5 shared publicationsMarc Brockschmidt
Microsoft Research
5 shared publications
Latest Publications
- Open Access
- 24 July 2026
- Published by Springer Nature
- p. 136-155
Accelerating Loops with Arrays
We propose a novel acceleration technique for loops operating on arrays. The goal of acceleration is to characterize the transitive closure of loops in a logic which is suitable for automated reasoning. Using the new notion of inductive lvalues , our technique can handle loops where previous techniques fail, and it unifies acceleration for arrays and scalar variables by regarding scalars as arrays of dimension 0. Moreover, our approach uses $$\lambda $$ s instead of quantifiers. Then the resulting SMT problems can be solved via lemmas on demand . An empirical evaluation of our implementation in the tool shows the power of our approach.- 24 July 2026
- Published by Springer Nature
- p. 136-155
Open AccessAccelerating Loops with Arrays
We propose a novel acceleration technique for loops operating on arrays. The goal of acceleration is to characterize the transitive closure of loops in a logic which is suitable for automated reasoning. Using the new notion of inductive lvalues , our technique can handle loops where previous techniques fail, and it unifies acceleration for arrays and scalar variables by regarding scalars as arrays of dimension 0. Moreover, our approach uses $$\lambda $$ s instead of quantifiers. Then the resulting SMT problems can be solved via lemmas on demand . An empirical evaluation of our implementation in the tool shows the power of our approach. - Open Access
- 1 May 2026
- Published by Elsevier in Science of Computer Programming
- Vol. 253
Accelerated bounded model checking with LoAT
- 1 May 2026
- Published by Elsevier in Science of Computer Programming
- Vol. 253
Open AccessAccelerated bounded model checking with LoAT
- 15 April 2026
- Published by Springer Nature
- p. 131-150
On Deciding Constant Runtime of Linear Loops
- Open Access
On Deciding Constant Runtime of Linear Loops
We consider linear single-path loops of the form \[ \textbf{while} \quad \varphi \quad \textbf{do} \quad \vec{x} \gets A \vec{x} + \vec{b} \quad \textbf{end} \] where $\vec{x}$ is a vector of variables, the loop guard $\varphi$ is a conjunction of linear inequations over the variables $\vec{x}$, and the update of the loop is represented by the matrix $A$ and the vector $\vec{b}$. It is already known that termination of such loops is decidable. In this work, we consider loops where $A$ has real eigenvalues, and prove that it is decidable whether the loop's runtime (for all inputs) is bounded by a constant if the variables range over $\mathbb R$ or $\mathbb Q$. This is an important problem in automatic program verification, since safety of linear while-programs is decidable if all loops have constant runtime, and it is closely connected to the existence of multiphase-linear ranking functions, which are often used for termination and complexity analysis. To evaluate its practical applicability, we also present an implementation of our decision procedure.Open AccessOn Deciding Constant Runtime of Linear Loops
We consider linear single-path loops of the form \[ \textbf{while} \quad \varphi \quad \textbf{do} \quad \vec{x} \gets A \vec{x} + \vec{b} \quad \textbf{end} \] where $\vec{x}$ is a vector of variables, the loop guard $\varphi$ is a conjunction of linear inequations over the variables $\vec{x}$, and the update of the loop is represented by the matrix $A$ and the vector $\vec{b}$. It is already known that termination of such loops is decidable. In this work, we consider loops where $A$ has real eigenvalues, and prove that it is decidable whether the loop's runtime (for all inputs) is bounded by a constant if the variables range over $\mathbb R$ or $\mathbb Q$. This is an important problem in automatic program verification, since safety of linear while-programs is decidable if all loops have constant runtime, and it is closely connected to the existence of multiphase-linear ranking functions, which are often used for termination and complexity analysis. To evaluate its practical applicability, we also present an implementation of our decision procedure. - Open Access
- 30 July 2025
- Published by Springer Nature
- p. 468-489
Infinite State Model Checking by Learning Transitive Relations
We propose a new approach for proving safety of infinite state systems. It extends the analyzed system by transitive relations until its diameter D becomes finite, i.e., until constantly many steps suffice to cover all reachable states, irrespective of the initial state. Then we can prove safety by checking that no error state is reachable in D steps. To deduce transitive relations, we use recurrence analysis . While recurrence analyses can usually find conjunctive relations only, our approach also discovers disjunctive relations by combining recurrence analysis with projections . An empirical evaluation of the implementation of our approach in our tool shows that it is highly competitive with the state of the art.
- 30 July 2025
- Published by Springer Nature
- p. 468-489
Open AccessInfinite State Model Checking by Learning Transitive Relations
We propose a new approach for proving safety of infinite state systems. It extends the analyzed system by transitive relations until its diameter D becomes finite, i.e., until constantly many steps suffice to cover all reachable states, irrespective of the initial state. Then we can prove safety by checking that no error state is reachable in D steps. To deduce transitive relations, we use recurrence analysis . While recurrence analyses can usually find conjunctive relations only, our approach also discovers disjunctive relations by combining recurrence analysis with projections . An empirical evaluation of the implementation of our approach in our tool shows that it is highly competitive with the state of the art.
- Open Access
- 11 September 2024
- Published by Springer Nature
- p. 73-91
Integrating Loop Acceleration Into Bounded Model Checking
Bounded Model Checking (BMC) is a powerful technique for proving unsafety. However, finding deep counterexamples that require a large bound is challenging for BMC. On the other hand, acceleration techniques compute “shortcuts” that “compress” many execution steps into a single one. In this paper, we tightly integrate acceleration techniques into SMT-based bounded model checking. By adding suitable “shortcuts” on the fly, our approach can quickly detect deep counterexamples. Moreover, using so-called blocking clauses, our approach can prove safety of examples where BMC diverges. An empirical comparison with other state-of-the-art techniques shows that our approach is highly competitive for proving unsafety, and orthogonal to existing techniques for proving safety.
- 11 September 2024
- Published by Springer Nature
- p. 73-91
Open AccessIntegrating Loop Acceleration Into Bounded Model Checking
Bounded Model Checking (BMC) is a powerful technique for proving unsafety. However, finding deep counterexamples that require a large bound is challenging for BMC. On the other hand, acceleration techniques compute “shortcuts” that “compress” many execution steps into a single one. In this paper, we tightly integrate acceleration techniques into SMT-based bounded model checking. By adding suitable “shortcuts” on the fly, our approach can quickly detect deep counterexamples. Moreover, using so-called blocking clauses, our approach can prove safety of examples where BMC diverges. An empirical comparison with other state-of-the-art techniques shows that our approach is highly competitive for proving unsafety, and orthogonal to existing techniques for proving safety.
- Open Access
- 1 July 2024
- Published by Springer Nature
- p. 344-365
Satisfiability Modulo Exponential Integer Arithmetic
SMT solvers use sophisticated techniques for polynomial (linear or non-linear) integer arithmetic. In contrast, non-polynomial integer arithmetic has mostly been neglected so far. However, in the context of program verification, polynomials are often insufficient to capture the behavior of the analyzed system without resorting to approximations. In the last years, incremental linearization has been applied successfully to satisfiability modulo real arithmetic with transcendental functions. We adapt this approach to an extension of polynomial integer arithmetic with exponential functions. Here, the key challenge is to compute suitable lemmas that eliminate the current model from the search space if it violates the semantics of exponentiation. An empirical evaluation of our implementation shows that our approach is highly effective in practice.
- 1 July 2024
- Published by Springer Nature
- p. 344-365
Open AccessSatisfiability Modulo Exponential Integer Arithmetic
SMT solvers use sophisticated techniques for polynomial (linear or non-linear) integer arithmetic. In contrast, non-polynomial integer arithmetic has mostly been neglected so far. However, in the context of program verification, polynomials are often insufficient to capture the behavior of the analyzed system without resorting to approximations. In the last years, incremental linearization has been applied successfully to satisfiability modulo real arithmetic with transcendental functions. We adapt this approach to an extension of polynomial integer arithmetic with exponential functions. Here, the key challenge is to compute suitable lemmas that eliminate the current model from the search space if it violates the semantics of exponentiation. An empirical evaluation of our implementation shows that our approach is highly effective in practice.
- Open Access
- 6 April 2024
- Published by Springer Nature
- p. 206-228
From Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting
There are many evaluation strategies for term rewrite systems, but proving termination automatically is usually easiest for innermost rewriting. Several syntactic criteria exist when innermost termination implies full termination. We adapt these criteria to the probabilistic setting, e.g., we show when it suffices to analyze almost-sure termination (AST) w.r.t. innermost rewriting to prove full AST of probabilistic term rewrite systems. These criteria also apply to other notions of termination like positive AST. We implemented and evaluated our new contributions in the tool .
- 6 April 2024
- Published by Springer Nature
- p. 206-228
Open AccessFrom Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting
There are many evaluation strategies for term rewrite systems, but proving termination automatically is usually easiest for innermost rewriting. Several syntactic criteria exist when innermost termination implies full termination. We adapt these criteria to the probabilistic setting, e.g., we show when it suffices to analyze almost-sure termination (AST) w.r.t. innermost rewriting to prove full AST of probabilistic term rewrite systems. These criteria also apply to other notions of termination like positive AST. We implemented and evaluated our new contributions in the tool .
- Open Access
From Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting
There are many evaluation strategies for term rewrite systems, but proving termination automatically is usually easiest for innermost rewriting. Several syntactic criteria exist when innermost termination implies full termination. We adapt these criteria to the probabilistic setting, e.g., we show when it suffices to analyze almost-sure termination (AST) w.r.t. innermost rewriting to prove full AST of probabilistic term rewrite systems (PTRSs). These criteria also apply to other notions of termination like positive AST. We implemented and evaluated our new contributions in the tool AProVE.
Open AccessFrom Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting
There are many evaluation strategies for term rewrite systems, but proving termination automatically is usually easiest for innermost rewriting. Several syntactic criteria exist when innermost termination implies full termination. We adapt these criteria to the probabilistic setting, e.g., we show when it suffices to analyze almost-sure termination (AST) w.r.t. innermost rewriting to prove full AST of probabilistic term rewrite systems (PTRSs). These criteria also apply to other notions of termination like positive AST. We implemented and evaluated our new contributions in the tool AProVE.
- Open Access
- 4 December 2023
- Published by Springer Nature in Formal Methods in System Design
- Vol. 65 (1-3) , 70-132
Termination of triangular polynomial loops
We consider the problem of proving termination for triangular weakly non-linear loops (twn-loops) over some ring $$\mathcal {S}$$ like $$\mathbb {Z}$$ , $$\mathbb {Q}$$ , or $$\mathbb {R}$$ . The guard of such a loop is an arbitrary quantifier-free Boolean formula over (possibly non-linear) polynomial inequations, and the body is a single assignment of the form $$\begin{bmatrix} x_1\\ \ldots \\ x_d \end{bmatrix} \leftarrow \begin{bmatrix} c_1 \cdot x_1 + p_1\\ \ldots \\ c_d \cdot x_d + p_d \end{bmatrix}$$ where each $$x_i$$ is a variable, $$c_i \in \mathcal {S}$$ , and each $$p_i$$ is a (possibly non-linear) polynomial over $$\mathcal {S}$$ and the variables $$x_{i+1},\ldots ,x_{d}$$ . We show that the question of termination can be reduced to the existential fragment of the first-order theory of $$\mathcal {S}$$ . For loops over $$\mathbb {R}$$ , our reduction implies decidability of termination. For loops over $$\mathbb {Z}$$ and $$\mathbb {Q}$$ , it proves semi-decidability of non-termination. Furthermore, we present a transformation to convert certain non-twn-loops into twn-form. Then the original loop terminates iff the transformed loop terminates over a specific subset of $$\mathbb {R}$$ , which can also be checked via our reduction. Moreover, we formalize a technique to linearize (the updates of) twn-loops in our setting and analyze its complexity. Based on these results, we prove complexity bounds for the termination problem of twn-loops as well as tight bounds for two important classes of loops which can always be transformed into twn-loops. Finally, we show that there is an important class of linear loops. where our decision procedure results in an efficient procedure for termination analysis, i.e., where the parameterized complexity of deciding termination is polynomial.- 4 December 2023
- Published by Springer Nature in Formal Methods in System Design
- Vol. 65 (1-3) , 70-132
Open AccessTermination of triangular polynomial loops
We consider the problem of proving termination for triangular weakly non-linear loops (twn-loops) over some ring $$\mathcal {S}$$ like $$\mathbb {Z}$$ , $$\mathbb {Q}$$ , or $$\mathbb {R}$$ . The guard of such a loop is an arbitrary quantifier-free Boolean formula over (possibly non-linear) polynomial inequations, and the body is a single assignment of the form $$\begin{bmatrix} x_1\\ \ldots \\ x_d \end{bmatrix} \leftarrow \begin{bmatrix} c_1 \cdot x_1 + p_1\\ \ldots \\ c_d \cdot x_d + p_d \end{bmatrix}$$ where each $$x_i$$ is a variable, $$c_i \in \mathcal {S}$$ , and each $$p_i$$ is a (possibly non-linear) polynomial over $$\mathcal {S}$$ and the variables $$x_{i+1},\ldots ,x_{d}$$ . We show that the question of termination can be reduced to the existential fragment of the first-order theory of $$\mathcal {S}$$ . For loops over $$\mathbb {R}$$ , our reduction implies decidability of termination. For loops over $$\mathbb {Z}$$ and $$\mathbb {Q}$$ , it proves semi-decidability of non-termination. Furthermore, we present a transformation to convert certain non-twn-loops into twn-form. Then the original loop terminates iff the transformed loop terminates over a specific subset of $$\mathbb {R}$$ , which can also be checked via our reduction. Moreover, we formalize a technique to linearize (the updates of) twn-loops in our setting and analyze its complexity. Based on these results, we prove complexity bounds for the termination problem of twn-loops as well as tight bounds for two important classes of loops which can always be transformed into twn-loops. Finally, we show that there is an important class of linear loops. where our decision procedure results in an efficient procedure for termination analysis, i.e., where the parameterized complexity of deciding termination is polynomial.