Title: An Overview of Recent Solutions to and Lower Bounds for the Firing Synchronization Problem,
Abstract: Complex systems in a wide variety of areas such as biological modeling, image
processing, and language recognition can be modeled using networks of very
simple machines called finite automata. Connecting subsystems modeled using
finite automata into a network allows for more computational power. One such
network, called a cellular automaton, consists of an n-dimensional array for n
> 1 with a single finite automaton located at each point of the array. One of
the oldest problems associated with cellular automata is the firing
synchronization problem, originally proposed by John Myhill in 1957. As with
any long-standing problem, there are a large number of solutions to the firing
synchronization problem. Our goal, and the contribution of this work, is to
summarize recent solutions to the problem. We focus primarily on solutions to
the original problem, that is, the problem where the network is a
one-dimensional array and there is a single initiator located at one of the
ends. We summarize both minimal-time and non-minimal-time solutions, with an
emphasis on solutions that were published after 1998. We also focus on
solutions that minimize the number of states required by the finite automata.
In the process we also identify open problems that remain in terms of finding
minimal-state solutions to the firing synchronization problem.