Title: | Firing Synchronization on the Ring |
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: | [ps, pdf] |