We introduce completely distinguishable automata, give different characterizations, and prove that for automata with at least three states they form a subclass of the synchronizing automata, i.e., those automata that can be synchronized into a definite state. For an n-state automaton, \(2^n - n\) states are sufficient to accept its set of synchronizing words, and we call the automaton sync-maximal if this number of states is also necessary. We prove that an automaton is sync-maximal if and only if it is completely distinguishable and contains a completely reachable subautomaton that only misses at most one state. Furthermore, we prove that a synchronizing automaton where every letter has defect at most one and whose transformation semigroup contains a transitive permutation group is completely distinguishable. As a consequence, a binary automaton with at least three states is completely reachable if and only if it is sync-maximal, which answers an open question from the literature. Then, we prove that an automaton with simple idempotents (SI-automaton) is completely reachable if and only if it is synchronizing and strongly connected, and that for SI-automata whose transformation monoid contains a transitive permutation group, synchronizability, complete reachability, complete distinguishability, and sync-maximality are equivalent properties. As a consequence, we obtain known characterizations of primitive groups in terms of these notions. Lastly, we prove that deciding each of the properties complete reachability, complete distinguishability, and sync-maximality are NL-hard for SI-automata without permutational letters.
