Binary completely reachable automata

Abstract

We characterize complete deterministic finite automata with two input letters in which every non-empty set of states occurs as the image of the whole state set under the action of a suitable input word. The characterization leads to a polynomial-time algorithm for recognizing this class of automata.

13 pages, 4 figures. A conference version of this paper has been accepted for LATIN 2022. The present version incorporates many useful comments and suggestions by the anonymous reviewers of the conference version