Cellular automata and communication complexity

DOI10.1016/j.tcs.2004.03.017zbMath1068.68087OpenAlexW2006286107MaRDI QIDQ1885923

Christoph Dürr, Guillaume Theyssier, Ivan Rapaport

Publication date: 12 November 2004

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

Full work available at URL: http://hdl.handle.net/10533/175112

zbMATH Keywords

Cellular automataCommunication complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Cellular automata (computational aspects) (68Q80)

Related Items

Unraveling simplicity in elementary cellular automata ⋮ An information-based classification of elementary cellular automata ⋮ Communication complexity and intrinsic universality in cellular automata ⋮ Communication complexity meets cellular automata: necessary conditions for intrinsic universality ⋮ Classifying 1D elementary cellular automata with the 0-1 test for chaos ⋮ Unnamed Item ⋮ Traced communication complexity of cellular automata ⋮ Communication complexity in number-conserving and monotone cellular automata ⋮ DESIGNING COMPLEX DYNAMICS IN CELLULAR AUTOMATA WITH MEMORY ⋮ Lower bounds and hardness magnification for sublinear-time shrinking cellular automata

Cites Work

• The Nilpotency Problem of One-Dimensional Cellular Automata
• Communication Complexity
• Unnamed Item
• Unnamed Item

This page was built for publication: Cellular automata and communication complexity