Some Research On The Extreme Synchronizing Automata

In this paper, we mainly study 3,4-state extreme synchronizing automata and n-state circular automata which n is a prime number, and some properties of aug-mentable subsets of the latter automata are given . At the meantime, we give the definition of defective letter and permutable letter. And by discussing the existence of them in extreme synchronizing automata, we find 27 kinds of 3,4-state extreme synchronizing automata including 8 kinds of extreme essential synchronizing au-tomata we have known. There are three chapters , the main contest are given in follow:In the first chapter, we give the introductions and preliminaries.In the second chapter, We proved that the m-state subsets of n-state circular automata's states sets are n-augmentable if (m,n)=1 by the method of matrix representation and transformation. And one of the specific forms of the shortest synchronizing words is given. By using the results we have obtained, we can directly get the results about prime order synchronizing circular automata which Pin has given. The main results are given in follow:Theorem 2.2.1 Let A = (Q,?, ?, be an n-state circular automaton, a, b be a circular letter and a defective letter of A, respectively, P be an m order non empty proper subset of Q. If (m,n)=1, then there is a augmentable word of P just like the form of bai (0?i?n-1).In the third chapter: we mainly study 3,4-state extreme synchronizing automar ta. At first, some common features of them axe given respectively. And then we analyse the extreme synchronizing automata according to the number of tracks of permutable letters contained in them. Finally, we find 27 kinds of extreme synchro-nizing automata, 8 kinds of extreme essential synchronizing automata are included.The main result is given in follow:Theorem 3.2.1 Up to isomorphism, there are 15 kinds of 3-state extreme synchronizing automata. 4 kinds of them are essential extreme synchronizing au-tomata that have existed in Fig.1, and 11 kinds of them are non-essential extreme synchronizing automata that haven't given in Fig.1.Lemma 3.2.2 Let A = (Q, ?, ?) be an arbitrary 3-state extreme synchroniz-ing automaton, whereand ?1 is the set of permutable letters, ?2 is the set of defective letters where the defect of any letter in it is one, E3 is the set of defective letters where the defect of any letter in it is two. Then we have(1) ?3 = (?), ?2?(?);(2) for any b ? E2, Qb2 = Qb;(3) there is a unique defected state in A;(4)?1?(?).Theorem 3.3.1 Up to isomorphism, there are 12 kinds of 3-state extreme synchronizing automata. 2 kinds of them are essential extreme synchronizing au-tomata that have existed in Fig-1, and 10 kinds of them are non-essential extreme synchronizing automata that haven't given in Fig.1.Lemma 3.3.2 Let A = (Q, E, ?) be an arbitrary 4-state extreme synchroniz-ing automaton, whereand ?1 is the set of permutable letters, ?2 is the set of defective letters where the defect of any letter in it is one, E3 is the set of defective letters where the defect of any letter in it is two, ?4 is the set of defective letters where the defect of any letter in it is three. Then we have(1) ?3 = (?), ?4 = (?), ?2?(?);(2) for any b? ?2, Qb2 = Qb;(3) there is a unique defected state in A;(4)?1?(?).