Gilles Dowek (INRIA)
Personal webpage: https://who.rocq.inria.fr/Gilles.Dowek
Cut-elimination and the decidability of reachability in alternating pushdown systems
Proof theory and automata theory both provide methods to prove decidability results. We will show in this talk that, despite differences in their presentation, some proof-theoretical and automata-theoretical methods essentially are the same. More precisely, we will give a new proof of the decidability of accessibility in alternating pushdown systems, showing that it is a consequence of a cut-elimination theorem for a natural-deduction like system.
Real numbers, chaos, and the principle of a bounded density of information
Two definitions of the notion of a chaotic transformation are compared: sensitivity to initial conditions and sensitivity to perturbations. Only the later is compatible with the idea that information has a finite density.