2017/08/16 by Rodaro, Emanuele
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1708.04864
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 (1)/(4)min\|u|: u∈ I\+(1)/(16) has a reset word of length at most (n-(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=Σ*MΣ*. With this tool, we first show the existence of an infinite strongly connected synchronizing automaton 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 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 (kmk)2^kmkn states, where k=|Σ|, 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 O((k2mk)2^kmkn).