A single-copy minimal-time simulation of a torus of automata by a ring of automata

DOI10.1016/j.dam.2007.05.019zbMath1122.68474OpenAlexW2083642090MaRDI QIDQ2384397

Claudine Peyrat, Bruno Martin

Publication date: 21 September 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.05.019

zbMATH Keywords

complexityCayley graphsCellular automata

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Cellular automata (computational aspects) (68Q80)

Cites Work

• Reversible simulation of one-dimensional irreversible cellular automata
• A six-state minimal time solution to the Firing squad synchronization problem
• A linear speed-up theorem for cellular automata
• Amenable groups and cellular automata
• Complexity and decidability
• A universal cellular automaton in quasi-linear time and its S-m-n form
• Simple 8-state minimal time solution to the firing squad synchronization problem
• Embedding Torus Automata into a Ring of Automata
• Garden of Eden Configurations for Cellular Automata on Cayley Graphs of Groups
• The firing squad synchronization problem on Cayley graphs
• A simulation of cellular automata on hexagons by cellular automata on rings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A single-copy minimal-time simulation of a torus of automata by a ring of automata