Other
A Symmetric Nine-State Automaton for the Generalized Firing Synchronization Problem
(1997)
Abstract
The firing synchronization problem was introduced by J.Myhill in 1957. The problem concerns a one-dimensional array of finite automata. The length of the array of automata is denoted by n. All automata are identical except for the ones on the end, one of which is the initiator for the synchronization. The goal is to define the set of states and transition rules for the automata so that all machines enter a special fire state for the first time and simultaneously at some time t(n). The generalized firing synchronization problem was introduced in 1968 by F.R. Moore and G.G. Langdon. This problem differs from the original firing synchronization problem in that the initiator of the synchronization can be located anywhere in the array. The generalized problem requires time 2n-k-2, where n is the number of automata in the array and k is the distance from the initiator to the nearest end of the array. H. Szwerinski, using ideas similar to Moore and Langdon''s, produced a ten-state, minimal-time, symmetric solution. We improve on that automaton to produce the first known nine-state, time-optimal, symmetric solution.
Disciplines
Publication Date
May 2, 1997
Citation Information
A. Settle. A Symmetric Nine-State Automaton for the Generalized Firing Synchronization Problem, Department of Computer Science Technical Report 97-03, University of Chicago, May 2, 1997.