Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words

DOI10.1007/978-3-030-68195-1_24arXiv2007.09104MaRDI QIDQ6345307FDOQ6345307

Authors: Stefan Hoffmann 

Publication date: 17 July 2020

Abstract: 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 $6leklen-6$ is either the alternating or the symmetric group.

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

This page was built for publication: Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345307)