FFFlorian Frohn

Florian Frohn

*This is an algorithmically generated author record based on publicly available information.

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


Florian Frohn has a total of 23 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Accelerating Loops with Arrays

    by Florian Frohn, Jürgen Giesl

    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.

  • On Deciding Constant Runtime of Linear Loops

    by Florian Frohn, Jürgen Giesl, Peter Giesl, Nils Lommen

  • Open Access

    On Deciding Constant Runtime of Linear Loops

    by Florian Frohn, Jürgen Giesl, Peter Giesl, Nils Lommen

    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

    Infinite State Model Checking by Learning Transitive Relations

    by Florian Frohn, Jürgen Giesl

    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

    Integrating Loop Acceleration Into Bounded Model Checking

    by Florian Frohn, Jürgen Giesl

    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

    Satisfiability Modulo Exponential Integer Arithmetic

    by Florian Frohn, Jürgen Giesl

    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

    From Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting

    by Jan-Christoph Kassing, Florian Frohn, Jürgen Giesl

    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

    by Jan-Christoph Kassing, Florian Frohn, Jürgen Giesl

    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

    Termination of triangular polynomial loops

    by Marcel Hark, Florian Frohn, Jürgen Giesl

    We consider the problem of proving termination for triangular weakly non-linear loops (twn-loops) over some ring $$\mathcal {S}$$ S like $$\mathbb {Z}$$ Z , $$\mathbb {Q}$$ Q , or $$\mathbb {R}$$ 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}$$ x 1 … x d ← c 1 · x 1 + p 1 … c d · x d + p d where each $$x_i$$ x i is a variable, $$c_i \in \mathcal {S}$$ c i ∈ S , and each $$p_i$$ p i is a (possibly non-linear) polynomial over $$\mathcal {S}$$ S and the variables $$x_{i+1},\ldots ,x_{d}$$ x i + 1 , … , x d . We show that the question of termination can be reduced to the existential fragment of the first-order theory of $$\mathcal {S}$$ S . For loops over $$\mathbb {R}$$ R , our reduction implies decidability of termination. For loops over $$\mathbb {Z}$$ Z and $$\mathbb {Q}$$ 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}$$ 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.