Speaker
Description
Robert Ferens and Marek Szykuła
Abstract: A complete deterministic finite (semi)automaton (DFA) with a set of states $Q$ is \emph{completely reachable} if every non-empty subset of $Q$ can be obtained as the image of the action of some word applied to $Q$.
The concept of completely reachable automata appeared several times, in particular, in connection with synchronizing automata; the class contains the \Cerny automata and covers a few separately investigated subclasses.
The notion was introduced by Bondar and Volkov (2016), who also raised the question about the complexity of deciding if an automaton is completely reachable.
We develop a polynomial-time algorithm for this problem, which is based on a new complement-intersecting technique for finding an extending word for a subset of states.
The algorithm works in $O(|\Sigma|\cdot n^3)$ time, where $n=|Q|$ is the number of states and $|\Sigma|$ is the size of the input alphabet.
Finally, we prove a weak Don's conjecture for this class of automata: a subset of size $k$ is reachable with a word of length at most $2\cdot(n-k)\cdot n$.
This implies a quadratic upper bound in $n$ on the length of the shortest synchronizing words (reset threshold) for the class of completely reachable automata and generalizes earlier upper bounds derived for its subclasses.