2020/04/19 by Ruszil, Jakub
#68Q45 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2004.08801
A goal of this paper is to introduce the new construction of an automaton with shortest synchronizing word of length O(d(n)/(d)), where d ∈ ℕ and n is the number of states for that automaton. Additionally we introduce new transformation from any synchronizable DFA or carefully synchronizable PFA of n states to carefully synchronizable PFA of d ⋅ n states with shortest synchronizing word of length Ω(d(n)/(d)).