arrow-right host location public time type
Nov 2021

Rice Theorems for Automata Networks and Succinct Graphs

Tipo de Evento: Seminario
Organiza: Facultad de Ingeniería y Ciencias
Dónde: Vía Zoom
Público: Estudiantes
Horario: 11:30:00 hr
Accede aquí

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.


Redes Sociales