Webpage of the Compositional Systems and Methods group at TalTech.

9 December 2021 14:00, online


Thomas Seiller


Linear realisability, dynamical systems and lower bounds in complexity


I will provide an overview of my recent (and not so recent) work studying connections between dynamical systems, logic and computation, with an emphasis on two recent results. The first exhibits a connection between linear negation and zeta functions of dynamical systems, something that can be exploited to build a model of second-order linear logic based on (discrete and continuous) Markov processes. The second unveils a connection between computational complexity and topological entropy, allowing to give an abstract account of several previous lower bounds results and strengthening one of the strongest complexity lower bounds previously known.