A system- and language-theoretic outlook on cellular automata

Silvio Capobianco

Thursday, 27 November 2008, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B101

Slides from the talk [pdf]

Abstract: Conceived by John von Neumann in the 1950s while searching for a model of self-reproduction, cellular automata (CA) describe transformations of global configurations on regular grids in terms of finite-range interactions between the nodes of the grid. The structure of the CA paradigm allows manifold applications in physics and biology as well as social sciences. Also, a wide range of CA-related theoretical studies exists, with connections to several fields of theoretical computer science and dynamical systems theory. This talk is aimed at providing an outlook on cellular automata, focusing on subjects linked to language theory and symbolic dynamics. After a short introduction, we illustrate some facts and problems in CA theory, together with classical and recent results.

Tarmo Uustalu
Last update 30.11.2008