Exploring millions of 6-state FSSP solutions: the formal notion of local CA simulation

DOI10.1007/978-3-030-61588-8_1MaRDI QIDQ2038007zbMATH OpenOpenAlexFDO

Authors Tien Thao Nguyen, Luidnel Maignan

Publication date 8 July 2021

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

zbMATH Keywords

automata minimizationcellular automatafiring squad synchronization problem

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Abstract: In this paper, we come back on the notion of local simulation allowing to transform a cellular automaton into a closely related one with different local encoding of information. This notion is used to explore solutions of the Firing Squad Synchronization Problem that are minimal both in time (2n -- 2 for n cells) and, up to current knowledge, also in states (6 states). While only one such solution was proposed by Mazoyer since 1987, 718 new solutions have been generated by Clergue, Verel and Formenti in 2018 with a cluster of machines. We show here that, starting from existing solutions, it is possible to generate millions of such solutions using local simulations using a single common personal computer.

Recommendations

• About 4-States Solutions to the Firing Squad Synchronization Problem
• Seven-state solutions to the firing squad synchronization problem
• A new class of the smallest FSSP partial solutions for 1D rings of length \(n=2^k-1\)
• scientific article; zbMATH DE number 4072387
• The smallest FSSP partial solutions for one-dimensional ring cellular automata: symmetric and asymmetric synchronizers

Cited in

(1)

• Millions of 5-State $$n^3$$-Real Time Sequence Generators via Local Simulations

This page was built for publication: Exploring millions of 6-state FSSP solutions: the formal notion of local CA simulation

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