Traced communication complexity of cellular automata

Eric Goles, Pierre Guillon, Ivan Rapaport

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

3 Citas (Scopus)

Resumen

We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata.

Idioma originalInglés
Páginas (desde-hasta)3906-3916
Número de páginas11
PublicaciónTheoretical Computer Science
Volumen412
N.º30
DOI
EstadoPublicada - 8 jul. 2011
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'Traced communication complexity of cellular automata'. En conjunto forman una huella única.

Citar esto