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 }^{\ast }M{\Sigma }^{\ast }$. 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 $(k{m}^k)2^{k{m}^{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^{k{m}^{k}n})$.

17 pages

References in corpus (1)

• Reset Complexity of Ideal Languages