Subset synchronization and careful synchronization of binary finite automata (Q2833542)

A reset word of a finite automaton is an input sequence that brings the automaton to a unique given state, no matter in which state the computation starts. A finite automaton is synchronizing if it has a reset word. The well-known open Černý conjecture claims that any \(n\)-state deterministic synchronizing finite automaton has a reset word of length at most \(\left( n-1\right) ^{2}\). The author investigates two generalizations of this problem. The first one deals with careful (using only the defined transitions) reset words of partial finite automata and the second one with reset words for synchronizing an automaton being in a state belonging to some fixed subset of its states. In both cases it is shown that the lower bound for the length of the reset word for \(n\)-state automata with binary input alphabet is exponential (\(2^{\Omega\left( n\right) }\)). This improves the previous results based on automata with a growing size of the input alphabet.