Gunther Cornelissen: Solving equations using Turing machines

Tid: On 2020-02-19 kl 11.00

Föreläsare: Gunther Cornelissen, Utrecht

Plats: Kräftriket, house 5, room 31

Abstract

It is relevant for various problems in group theory and algebraic geometry to construct explicit power series (with coefficients in a finite field) that are of finite order under composition. Only a handful of examples is known. We give a finite deterministic description of such series using automata (a kind of memoryless Turing machine), based on finding algebraic equation for such series and using a theorem of Christol. We then we study various complexity measures of the associated series (for example, what is the number of states, what is the density of non-vanishing coefficients?). Joint work with Jakub Byszewski (Krakow) and Djurre Tijsma (Dusseldorf).

Innehållsansvarig:webmaster@math.kth.se
Tillhör: Institutionen för matematik
Senast ändrad: 2020-02-05