Automates cellulaires probabilistes


Guillaume Theyssier, LAMA, LIMD. 24 janvier 2013 10:00 limd 2:00:00
Abstract:

Les automates cellulaires probabilistes ou non-déterministes sont souvent étudiés à travers des exemples ou aspects particuliers (alpha-asynchronisme, automates bruités, transitions locales probabilistes, etc). Nous proposons au contraire de les formaliser dans un modèle général qui se prête à une étude systématique. Partant de là nous abordons deux problématiques importantes largement développées dans la théorie des automates cellulaires déterministes : les simulations et l'universalité intrinsèque d'une part, la décidabilité des propriétés globales en fonction des descriptions locales d'autre part.