Title: Synchronizing automata and the language of minimal reset words,
Abstract: We study a connection between synchronizing automata and its set $M$ of
minimal reset words, i.e., such that no proper factor is a reset word. We first
show that any synchronizing automaton having the set of minimal reset words
whose set of factors does not contain a word of length at most
$\frac{1}{4}\min\{|u|: u\in I\}+\frac{1}{16}$ has a reset word of length at
most $(n-\frac{1}{2})^{2}$ In the last part of the paper we focus on the
existence of synchronizing automata with a given ideal $I$ that serves as the
set of reset words. To this end, we introduce the notion of the tail structure
of the (not necessarily regular) ideal $I=\Sigma^{*}M\Sigma^{*}$. With this
tool, we first show the existence of an infinite strongly connected
synchronizing automaton $\mathcal{A}$ having $I$ as the set of reset words and
such that every other strongly connected synchronizing automaton having $I$ as
the set of reset words is an homomorphic image of $\mathcal{A}$. Finally, we
show that for any non-unary regular ideal $I$ there is a strongly connected
synchronizing automaton having $I$ as the set of reset words with at most
$(km^{k})2^{km^{k}n}$ states, where $k=|\Sigma|$, $m$ is the length of a
shortest word in $M$, and $n$ is the dimension of the smallest automaton
recognizing $M$ (state complexity of $M$). This automaton is computable and we
show an algorithm to compute it in time $\mathcal{O}((k^{2}m^{k})2^{km^{k}n})$.