2016/01/17 by Artur Schaefer, Schaefer, Artur
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1601.04295
openalex publication_date 2016/01/17 · openalex created_date 2022/08/30 · openalex updated_date 2026/07/28
This paper analyses the construction of the kernel graph of a\nnon-synchronizing transformation semigroup and introduces the inverse\nsynchronization problem. Given a transformation semigroup S\≤ Tn, we\nconstruct the kernel graph \Gr(S) by saying v and w are adjacent,\nif there is no f\∈ S with vf=wf. The kernel graph is trivial or complete\nif the semigroup is a synchronizing semigroup or a permutation group,\nrespectively. The connection between graphs and synchronizing (semi-) groups\nwas established by Cameron and Kazanidis, and it has led to many results\nregarding the classification of synchronizing permutation groups, and the\ndescription of singular endomorphims of graphs. This paper, firstly, emphasises\nthe importance of this construction mainly by proving its superior structure,\nsecondly, analyses the construction and discusses minimal generating sets and\ntheir combinatorial properties, and thirdly, introduces the inverse\nsynchronization problem. The third part also includes an additional\ncharacterization of primitive groups.\n