Localisation

Adresses

Aix-Marseille Université
Institut de Mathématiques de Marseille (I2M) - UMR 7373
Site Saint-Charles : 3 place Victor Hugo, Case 19, 13331 Marseille Cedex 3
Site Luminy : Campus de Luminy - Case 907 - 13288 Marseille Cedex 9

Séminaire

Rice-like theorems for automata networks – Guilhem Gamard

Guilhem Gamard
LIS, Marseille
http://www.mlir.info/gamard/

Date(s) : 03/11/2020   iCal
11h00 - 12h00

Titre : Rice-like theorems for automata networks

Résumé :

An automata network (AN for short) is a finite digraph where each node holds a state, choosen 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 an 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.

 

VIRTUAL EVENT: https://bbb-test.univ-amu.fr/b/sar-xmr-npe

Emplacement
I2M Luminy - TPR2, Salle de Séminaire 304-306 (3ème étage)

Catégories


Secured By miniOrange