A Minimal Time Solution to the Firing Squad Synchronization Problem with Von Neumann Neighborhood of Extent 2

Kathryn Boddie
University of Wisconsin-Milwaukee
PhD Graduate Student – Dissertator

“Cellular automata provide a simple environment in which to study global behaviors. One example of a problem that utilizes cellular automata is the Firing Squad Synchronization Problem, first proposed in 1957. We will provide an overview of the standard Firing Squad Synchronization Problem and a commonly used technique in solving it. A new extension of the Standard Firing Squad Synchronization Problem to a different neighborhood definition – a Von Neumann neighborhood of extent 2 will be presented. An 8 state 651 rule minimal time solution to the extended problem will described and presented, along with an outline of the proof of the correctness of the solution.”

Committee Members:
Profs. Bruce Wade (Advisor); Suzanne Boyd, Christine Cheng, Istvan Lauko, & Jeb Willenbring