Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Entire DC Network
Bounding The Firing Synchronization Problem On A Ring, André Berthiaume, Todd Bittner, Ljubomir Perković, Amber Settle, Janos Simon
Bounding The Firing Synchronization Problem On A Ring, André Berthiaume, Todd Bittner, Ljubomir Perković, Amber Settle, Janos Simon
Amber Settle
In this paper we improve the upper and lower bounds on the complexity of solutions to the firing synchronization problem on a ring. In this variant of the firing synchronization problem the goal is to synchronize a ring of identical finite automata. Initially, all automata are in the same state except for one automaton that is designated as the initiator for the synchronization. The goal is to define the set of states and the transition function for the automata so that all machines enter a special fire state for the first time and simultaneously during the final round of the …