Article
Bounding the firing synchronization problem on a ring
Theoretical Computer Science
(2004)
Abstract
In this paper we improve the upper and lower bounds on the complexity of solutions to the firing synchronization problem on a ring. In this variant of the firing synchronization problem the goal is to synchronize a ring of identical finite automata. Initially, all automata are in the same state except for one automaton that is designated as the initiator for the synchronization. The goal is to define the set of states and the transition function for the automata so that all machines enter a special fire state for the first time and simultaneously during the final round of the computation. In our work we present two solutions to the ring firing synchronization problem, an 8-state minimal-time solution and a 6-state non-minimal-time solution. Both solutions use fewer states than the previous best-known minimal-time automaton, a 16-state solution due to Culik. We also give the first lower bounds on the number of states needed for solutions to the ring firing synchronization problem. We show that there is no 3-state solution and no 4-state, symmetric, minimal-time solution for the ring.
Keywords
- Cellular automata,
- Firing squad synchronization problem,
- Finite automata
Disciplines
Publication Date
June 14, 2004
DOI
10.1016/j.tcs.2004.01.036
Citation Information
André Berthiaume, Todd Bittner, Ljubomir Perković, Amber Settle, et al.. "Bounding the firing synchronization problem on a ring" Theoretical Computer Science Vol. 320 Iss. 2-3 (2004) p. 213 - 228 ISSN: 0304-3975 Available at: http://works.bepress.com/asettle/56/