Abstract

Title: Firing Synchronization on the Ring
Published: January 2002
Authors: André Berthiaume, Ljubomir Perkovic, Amber Settle, Janos Simon
Abstract:

We present two solutions to the firing synchronization problem on the ring, 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.

Full Paper: [postscript, pdf]