Some Remarks on Synchronization, Games and Planar Automata
J. Andrés Montoya, Christian Nolasco · Electronic Notes in Theoretical Computer Science · 2018
We study synchronization games on planar automata. We prove that recognizing the planar games that can be won by the synchronizer is a co-NP hard problem. We prove some additional results indicating that planar games are as hard as nonplanar games. Those results amount to show that planar automata are representative of the intricacies of automata synchronization.