On the synchronization of planar automata

Abstract

Planar automata seems to be representative of the synchronizing behavior of deterministic finite state automata. We conjecture that Černy's conjecture holds true, if and only if, it holds true for planar automata. In this paper we have gathered some evidence concerning this conjecture. This evidence amounts to show that the class of planar automata is representative of the algorithmic hardness of synchronization

arXiv comment17 pages, 2 figures