The classical Rice theorem on Turing machine states that any non-trivial property of functions computed by Turing machines is undecidable. This talk is about similar results in the realm of automata networks using computational complexity instead of computability. We will present three versions of such Rice-like theorems: about limit sets of configurations, first order logic and monadic second order logic on the dynamics. In the last two cases, the results can be seen as statements about succinct graphs. This is a joint work with G. Gamard, P. Guillon and K. Perrot.
Chargé de recherche, CNRS, Team GDAC, Institut de Mathématiques de Marseille, Université Aix-Marseille.