| It is an important project to study the relationship about the property between transfor-mation semigroups and permutation groups,and to apply transformation semigroup theory to automata.In this paper,on the basis of the previous research we systematically study this topic,obtain some results and develop some the predecessors’ work.The main results are:we establish the relationship between complete regular semigroups and synchronous semigroups,and obtian some characterizations;we study the primitive property of permuta-tion groups and its application in the synchronous semigroup,and obtain some discriminant conditions;we study the relation between the imprimitive group and the synchronous semi-group,and depict some special cases;we study the almost synchronous group,and solve two open questions.The thesis is divided into five chaptersThe first chapter is devoted to surveying research background,results,methods in this area.In the second chapter,we mainly study the structure of completely regular semigroups and the relationship between completely regular semigroups and synchronizing semigroups.Let Tn and Sn be the full transformation semigroup and the symmetric group on the finite set Xn ＝ {1,2,...,n},respectively.Suppose that G is a subgroup of Sn and α∈Tn\Sn.Let S be a subsemigroup of Tn.A semigroup S is said to be completely regular if each element belongs to a subgroup.A semigroup S is said to be synchronizing if it contains a constant map.A group G synchronizes the transformation a if the semigroup<G,α)contains a constant map where α ∈ Tn\Sn,and G is a synchronizing group if G synchronizes all α ∈ Tn\Sn;non-synchronizing otherwise.Define the rank of α by |im(α)|,denote |im(α)| by rank(α).Let H be Green’s relation H.We have:(1)if(α,e)∈H,then<G,α>is a completely regular semigroup if and only if rank(aga)= rank(α)for all g ∈ G;(2)for G being a transitive group,<G,α>is a completely regular semigroup if and only if G is a transitive imprimitive group or a non-synchronizing primitive group;(3)if<G,α>is a completely regular semigroup for a being not constant,then<G,α>is a non-synchronizing semigroup;(4)for different kind of groups G,we consider<G,α>being completely regular semigroups;(5)by GAP,we partially classify the non-synchronizing primitive groups with index 2(see tables 1-4).In the third chapter,we consider that when<G,α>is a primitive group for G being a transitive imprimitive group and a∈Sn\G.We give many examples for<G,α>being(imprimitive)primitive groups.Meanwhile,we find that<G,α>being primitive groups and<G,α>being synchronizing semigroups are equivalence in some special cases.In the fourth chapter,we consider synchronizing semigroups which generated by differ-ent kind of set A(A(?)Tn\Sn or A = {G,α}).In particular,we try to determine when<G,α>is synchronizing for G being a transitive imprimitive group.We find that imprimitive groups G still synchronizes α for them being given rank or kernel style.We give many examples for<G,α>being(non-synchronizing)synchronizing semigroups.Meanwhile,we determine when<G,α>is non-synchronizing semigroup.In the fifth chapter,we study almost synchronizing group.Let G ≤Sn be a primitive group.If the parts of the kernel all have the same size,then a is called uniform;it is non-uniform otherwise.A group is said to be almost synchronizing if it synchronizes every non-uniform transformations.Given a set T(?)Xn with 1<|T|<n,we define a graph ΓT on the vertex set Xn by the rule that two distinct vertices x and y are adjacent if and only if there is an element g ∈G with {x,y}g(?)T.Following the standard convention,the complement ofΓT will be denoted ΓT we will denote adjacency in ΓT by～.The closed neighborhood of x in Twill be denoted by ΓT[x]= {x} ∪ {y|x～y}.Let P be a part of a G-regular partition p(see[41])and T be a G-regular section.we define m(T,P)= min{|A|:A(?)P,∩x∈A,ΓT[x]=P};and set m(G)to be the maximum of m(T,P)for all such pairs(T,P).For two distinct G-non-synchronizing partitions ρ and σ of the same rank k,let M(ρ,σ)=|ρ∩σ|/k,and set M(G)to be the maximum over all such pairs.we solve two problems which putted forward by Araujo et al([39]),that is,Problem 1.Is it true that m(G)= 2 implies M(G)≤1/2?Problem 2.Is it possible to prove Theorem 7([39])without any assumption about M(G)?... |
