moteur de recherche

Séminaire Algo - Guilhem Gamard
Séminaire Algo - Guilhem Gamard
9-Mar-2021 14:00
Age: 43 days

Guilhem Gamard

Rice-like theorems for automata networks

Zoom (if you want to participate, please request the meeting password. If your interest in the seminar is more general, you can request to be added to the announcement mailing list which will contain the password for each meeting)

An automata network (AN for short) is a finite digraph where each node holds a state, chosen among a finite set, that evolves in function of the states of its inbound neighbors. Time is discrete and all nodes evolve synchronously and in parallel, similarly to what happens in a cellular automaton. In other terms, the differences between a cellular automaton and an automata network is that the"grid" is an arbitrary finite digraph, and that different nodes may have different update functions. ANs have been used to model neural networks, dynamics of expression and inhibition of genes,distributed algorithms, and more. Although ANs look like a model of computation, they are not Turing-complete, for they lack unbounded memory. Still, they are subject to some kind of "Rice theorems", i.e., results along the lines of:"any nontrivial property of the function computed by an automata network is computationally hard to test". In this talk, we will review several results that fit this pattern, as well as pieces of proof that hopefully may be reused in other contexts.

<- Back to: Accueil