On synchronization of partial automata
share
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).
READ FULL TEXT