============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Stochastic cellular automata vs Probabilistic 
	     cellular automata
            
Palestrante: Nicolas Schabanel
             Université Paris Diderot

Hora e Data: 14h, sexta-feira, 25 de outubro de 2013

Local:       Sala Multi-usos do Numec

Resumo:

Cellular  automata  are commonly  used  to  model real  life
systems. Even if  most of he modeled systems  are random, we
still  lack  a  proper  definition for  randomized  cellular
automata. For  instance, the classic  probabilistic cellular
automata  (PCA) framework  has  several flaws  that we  will
highlight  with some  examples.  In particular  PCA fail  to
model  properly  number   conserving  systems  such  as  gas
lattice. We  thus define  the notion of  stochastic cellular
automata  (SCA) and  show how  it extends  strictly  the PCA
framework.  We will  also show  that the  two  models differ
considerably  by   exhibiting  simple  problems   which  are
decidable for PCA but indecidable for SCA.

Joint work with Pablo Arrighi and Guillaume Theyssier