Traced communication complexity of cellular automata

DOI10.1016/J.TCS.2011.02.025MaRDI QIDQ549703zbMATH OpenOpenAlexFDO

Authors Pierre Guillon, Ivan Rapaport, Eric Goles

Publication date 18 July 2011

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

Full work available at URL https://arxiv.org/abs/1102.3522, http://hdl.handle.net/10533/131576

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)

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.

Recommendations

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

Cites work

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

Cited in

(11)

• Number-conserving cellular automata and communication complexity: a numerical exploration beyond elementary CAs
• Communication complexity in number-conserving and monotone cellular automata
• Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol
• Trace complexity of chaotic reversible cellular automata
• Communications in cellular automata
• Cellular automata with sparse communication
• Communication complexity meets cellular automata: necessary conditions for intrinsic universality
• scientific article; zbMATH DE number 6502824 (Why is no real title available?)
• Computational complexity of the stability problem for elementary cellular automata
• Letting Alice and Bob choose which problem to solve: implications to the study of cellular automata
• Cellular automata and communication complexity

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)