Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.2/7114
Título: Between primitive and 2-transitive: synchronization and its friends
Autor: Araújo, João
Cameron, Peter J.
Steinberg, Benjamin
Palavras-chave: Permutation groups
Transformation semigroups
Automata
Synchronization
Primitivity
Data: 10-Dez-2017
Editora: European Mathematical Society Surveys in Mathematical Sciences
Resumo: An automaton is said to be synchronizing if there is a word in the transitions which sends all states of the automaton to a single state. Research on this topic has been driven by the Černý conjecture, one of the oldest and most famous problems in automata theory, according to which a synchronizing n-state automaton has a reset word of length at most (n-1)2. The transitions of an automaton generate a transformation monoid on the set of states, and so an automaton can be regarded as a transformation monoid with a prescribed set of generators. In this setting, an automaton is synchronizing if the transitions generate a constant map. A permutation group G on a set Ω is said to synchronize a map f if the monoid ⟨G,f⟩ fi generated by G and f is synchronizing in the above sense; we say G is synchronizing if it synchronizes every non-permutation. The classes of synchronizing groups and friends form an hierarchy of natural and elegant classes of groups lying strictly between the classes of primitive and 2-homogeneous groups. These classes have been floating around for some years and it is now time to provide a unified reference on them. The study of all these classes has been prompted by the Černý conjecture, but it is of independent interest since it involves a rich mix of group theory, combinatorics, graph endomorphisms, semigroup theory, finite geometry, and representation theory, and has interesting computational aspects as well. So as to make the paper self-contained, we have provided background material on these topics. Our purpose here is to present results that show the connections between the various areas of mathematics mentioned above, we include a new result on the Černý conjecture, some challenges to finite geometers, some thoughts about infinite analogues, and a long list of open problems.
Peer review: yes
URI: http://hdl.handle.net/10400.2/7114
DOI: 10.4171/EMSS/4-2-1
Aparece nas colecções:Matemática e Estatística - Artigos em revistas internacionais / Papers in international journals

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
1511.03184.pdf716,93 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.