Ponente: René Thiemann (University of Innsbruck)

Lugar: Seminario Mirian Andrés (Edificio CCT)

Hora: miércoles 15 de noviembre, 11:00

Resumen: Matrix interpretations are widely used in automated complexity analysis.
For these interpretations, certification boils down to
determining the growth rate of A^n for a fixed non-negative real
matrix A.

Since the direct approach to compute the growth rate of A
via algebraic numbers is quite slow, in this work we formalize
the Perron-Frobenius theorem: it permits us to avoid algebraic
numbers, so that our new certification algorithm only has to perform
simple arithmetic operations. To cover the theorem in its full extend,
we further establish a connection between two different Isabelle/HOL
libraries on matrices, which enables an easy exchange of theorems between
both libraries.

The slides of the talk are available from the following link.