Communication complexity in number-conserving and monotone cellular automata

DOI10.1016/j.tcs.2011.03.008zbMath1216.68172OpenAlexW1971688300MaRDI QIDQ551188

Ivan Rapaport, Andrés Moreira, Eric Goles Chacc

Publication date: 14 July 2011

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

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

zbMATH Keywords

cellular automatacommunication complexityelementary cellular automatanumber-conserving

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items

Communication complexity meets cellular automata: necessary conditions for intrinsic universality ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Asynchronous communicating cellular automata: formalization, robustness and equivalence ⋮ A decomposition theorem for number-conserving multi-state cellular automata on triangular grids ⋮ Unnamed Item ⋮ Eric Goles

Cites Work

• Unnamed Item
• Unnamed Item
• Traced communication complexity of cellular automata
• Communication complexity and intrinsic universality in cellular automata
• Universality and decidability of number-conserving cellular automata
• On conservative and monotone one-dimensional cellular automata and their particle representation
• Cellular automata and communication complexity
• Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol
• Cellular automaton rules conserving the number of active sites
• Conservation laws in cellular automata
• Communication Complexity