A six-state minimal time solution to the Firing squad synchronization problem
From MaRDI portal
Publication:1097699
DOI10.1016/0304-3975(87)90124-1zbMath0635.68042OpenAlexW2108002652WikidataQ29300723 ScholiaQ29300723MaRDI QIDQ1097699
Publication date: 1987
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(87)90124-1
systolic arrayfinite state automatafiring squad synchronizationminimization of the number of statesone-dimensional cellular structure
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)
Related Items (54)
THE FIRING SQUAD SYNCHRONIZATION PROBLEM ON SQUARES, TORUSES AND RINGS ⋮ Seven-state solutions to the firing squad synchronization problem ⋮ Grids and universal computations on one-dimensional cellular automata ⋮ Synchronization of 1-way connected processors ⋮ On optimal solutions to the firing squad synchronization problem ⋮ Automated theorem proving in mathematics. ⋮ A single-copy minimal-time simulation of a torus of automata by a ring of automata ⋮ Bounding the firing synchronization problem on a ring ⋮ Cutting the Firing Squad Synchronization ⋮ Minimum and non-Minimum Time Solutions to the Firing Squad Synchronization Problem ⋮ Time-Optimum Smaller-State Synchronizers for Cellular Automata ⋮ A design of generalized minimum-state-change FSSP algorithms and their implementations ⋮ Revisiting the cutting of the firing squad synchronization ⋮ A new reconstruction and the first implementation of Goto's FSSP algorithm ⋮ Implementations of FSSP Algorithms on Fault-Tolerant Cellular Arrays ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ State-efficient realization of fault-tolerant FSSP algorithms ⋮ An overview of quantum cellular automata ⋮ An intrinsically non minimal-time Minsky-like 6-states solution to the Firing Squad synchronization problem ⋮ A class of time-optimum FSSP algorithms for multi-dimensional cellular arrays ⋮ About 4-States Solutions to the Firing Squad Synchronization Problem ⋮ HOW TO SYNCHRONIZE THE ACTIVITY OF ALL COMPONENTS OF A P SYSTEM? ⋮ On hardest languages for one-dimensional cellular automata ⋮ A Compositional Approach to Synchronize Two Dimensional Networks of Processors ⋮ An efficient solution of the firing mob problem ⋮ Firing squad synchronization problem in reversible cellular automata ⋮ COMPUTATION OF A DETERMINANT AND A MATRIX PRODUCT IN CELLULAR AUTOMATA ⋮ A linear speed-up theorem for cellular automata ⋮ Abstract geometrical computation. 11: Slanted firing squad synchronisation on signal machines ⋮ Intrinsically universal \(n\)-dimensional quantum cellular automata ⋮ A 4-states algebraic solution to linear cellular automata synchronization ⋮ Partitioned quantum cellular automata are intrinsically universal ⋮ Faster synchronization in P systems ⋮ On the limit set of some universal cellular automata ⋮ A Seven-State Time-Optimum Square Synchronizer ⋮ Achieving Universal Computations on One-Dimensional Cellular Automata ⋮ On time optimal solutions of the firing squad synchronization problem for two-dimensional paths ⋮ Theory of cellular automata: a survey ⋮ The firing squad synchronization problem on Cayley graphs ⋮ Fast Synchronization in P Systems ⋮ On hardest languages for one-dimensional cellular automata ⋮ Constructible functions in cellular automata and their applications to hierarchy results ⋮ Leader election on two-dimensional periodic cellular automata ⋮ A new class of the smallest FSSP partial solutions for 1D rings of length \(n=2^k-1\) ⋮ A New Optimum-Time Firing Squad Synchronization Algorithm for Two-Dimensional Rectangle Arrays: One-Sided Recursive Halving Based ⋮ Computations on one-dimensional cellular automata ⋮ Simple 8-state minimal time solution to the firing squad synchronization problem ⋮ Signals in one-dimensional cellular automata ⋮ Generalized FSSP on Hexagonal Tiling: Towards Arbitrary Regular Spaces ⋮ Error detection and correction in firing squad synchronization problem ⋮ Different time solutions for the firing squad synchronization problem on basic grid networks ⋮ Synchronizing square arrays in optimum-time ⋮ The firing squad synchronization problem with sub-generals ⋮ Smaller solutions for the firing squad
Cites Work
This page was built for publication: A six-state minimal time solution to the Firing squad synchronization problem
