Skip to main content

Gunther Cornelissen: Solving equations using Turing machines

Time: Wed 2020-02-19 11.00

Lecturer: Gunther Cornelissen, Utrecht

Location: Kräftriket, house 5, room 31


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).

Belongs to: Department of Mathematics
Last changed: Feb 05, 2020