Some Remarks on Synchronization, Games and Planar Automata

摘要

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.