Traced communication complexity of cellular automata

DOI10.1016/J.TCS.2011.02.025zbMATH Open1216.68173arXiv1102.3522OpenAlexW2127828970MaRDI QIDQ549703FDOQ549703

Authors: Pierre Guillon, Ivan Rapaport, Eric Goles 

Publication date: 18 July 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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, expansiveness, entropy and give the asymptotic communication complexity of most elementary cellular automata.

Full work available at URL: https://arxiv.org/abs/1102.3522

Recommendations

• scientific article
• Communication complexity in number-conserving and monotone cellular automata
• Communications in cellular automata
• Cellular automata and communication complexity
• Cellular automata with sparse communication

zbMATH Keywords

cellular automatacommunication complexity

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Cellular automata (computational aspects) (68Q80)

Cites Work

• Languages, equicontinuity and attractors in cellular automata
• Bulking II: Classifications of cellular automata
• Communication complexity and intrinsic universality in cellular automata
• Communication Complexity
• Row subshifts and topological entropy of cellular automato
• On rank vs. communication complexity
• Cellular automata and communication complexity
• Ultimate traces of cellular automata
• Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol

Cited In (10)

• Computational complexity of the stability problem for elementary cellular automata
• Communication complexity in number-conserving and monotone cellular automata
• Title not available (Why is that?)
• Trace complexity of chaotic reversible cellular automata
• Cellular automata and communication complexity
• Cellular automata with sparse communication
• Letting Alice and Bob choose which problem to solve: implications to the study of cellular automata
• Communications in cellular automata
• Number-conserving cellular automata and communication complexity: a numerical exploration beyond elementary CAs
• Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol

This page was built for publication: Traced communication complexity of cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q549703)