Research On Extremal Synchronizing Circular Automata

Synchronizing automaton is a class of automata that is very familiar and widely used.The Cerny Conjecture about the shortest synchronizing words of synchronizing automaton is currently the longstanding open problem in the combinatorial theory of finite automata.For an automaton with at least three states,if the Cerny Conjecture is true,then the extremal synchronizing automaton(i.e.,the n-state synchronization automata whose shortest synchronizing words have length(n-1)2)is the extreme case of the synchronizing automaton.An extremal synchronizing automaton is called an extreme synchronizing automaton if it has only essential letters.The known extreme synchronizing automaton has only the Cerny automaton Cn(n?3)and other eight isolated examples.In 2006,A.N.Trahtman proposed the following conjecture based on relative experiments that there is no any unknown extreme synchronizing automaton on at least three states.Since the Cerny automata Cn(n?3)and one of the eight isolated examples mentioned as above are circular,it can be considered that almost all known extreme synchronizing automata are circular.Therefore,it may be helpful with the resolve of the Trahtman Conjecture and even the Cerny Conjecture to determine all extreme synchronizing circular automata.The aim of this paper is to determining not only all extreme synchronizing automata but also all extreme synchronizing automata.The main works of this paper include the following four steps:(1)Explore some important properties of the defective letters of extremal synchronizing circular automata,and then,according to such properties,classify the defective letters of extremal synchronizing circular automata into five types:bisecting,closing,semi-closing,opening and semi-opening.(2)Define the characteristic group of an extremal synchronizing circular automaton according to the properties of the defective letters of such an automaton,and reveals some characters of the order and the least generating element of the characteristic group.(3)Applying the characters of the characteristic groups of extremal synchronizing circular automata,determine the closing and semi-closing defective letters of extremal synchronizing circular automata,and prove by a series of complex combination analysis that any extremal synchronizing circular automaton has no bisecting,opening and semi-opening defective letters.(4)Determine all extremal synchronizing circular automata,and then confirm the Trahtman Conjecture for circular automata.