2020/07/17 by Hoffmann, Stefan
#68Q45 (Primary) 68Q19 (Secondary) 20B15 (Secondary) #F.1.3 #F.4.3 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR)
paper · doi:10.48550/arxiv.2007.09104
We give a new characterization of primitive permutation groups tied to the notion of completely reachable automata. Also, we introduce sync-maximal permutation groups tied to the state complexity of the set of synchronizing words of certain associated automata and show that they are contained between the 2-homogeneous and the primitive groups. Lastly, we define k-reachable groups in analogy with synchronizing groups and motivated by our characterization of primitive permutation groups. But the results show that a k-reachable permutation group of degree n with 6 ≤ k ≤ n - 6 is either the alternating or the symmetric group.