Geodesic
Between primitive and 2-transitive: Synchronization and its friends
João Araújo1 ; Peter J. Cameron2 ; Benjamin Steinberg3 orcid
1University of Lisbon, Portugal
2University of St Andrews, UK
3City College of New York, USA
EMS surveys in mathematical sciences, Tome 4 (2017) no. 2, pp. 101-184

Voir la notice de l'article provenant de la source EMS Press

DOI

An automaton (consisting of a finite set of states with given transitions) 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.
DOI : 10.4171/emss/4-2-1
Classification : 20-XX, 05-XX
Mots-clés : Primitive groups, synchronizing groups, spreading groups, separating groups, Černý conjecture, ovoids and spreads, graphs, orbitals, transformation semigroups, automata, 2-transitive

João Araújo  1   ; Peter J. Cameron  2   ; Benjamin Steinberg  3

1 University of Lisbon, Portugal
2 University of St Andrews, UK
3 City College of New York, USA 
João Araújo; Peter J. Cameron; Benjamin Steinberg. Between primitive and 2-transitive: Synchronization and its friends. EMS surveys in mathematical sciences, Tome 4 (2017) no. 2, pp. 101-184. doi: 10.4171/emss/4-2-1
@article{10_4171_emss_4_2_1,
     author = {Jo\~ao Ara\'ujo and Peter J. Cameron and Benjamin Steinberg},
     title = {Between primitive and 2-transitive: {Synchronization} and its friends},
     journal = {EMS surveys in mathematical sciences},
     pages = {101--184},
     year = {2017},
     volume = {4},
     number = {2},
     doi = {10.4171/emss/4-2-1},
     url = {http://geodesic.mathdoc.fr/articles/10.4171/emss/4-2-1/}
}
TY  - JOUR
AU  - João Araújo
AU  - Peter J. Cameron
AU  - Benjamin Steinberg
TI  - Between primitive and 2-transitive: Synchronization and its friends
JO  - EMS surveys in mathematical sciences
PY  - 2017
SP  - 101
EP  - 184
VL  - 4
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4171/emss/4-2-1/
DO  - 10.4171/emss/4-2-1
ID  - 10_4171_emss_4_2_1
ER  - 
%0 Journal Article
%A João Araújo
%A Peter J. Cameron
%A Benjamin Steinberg
%T Between primitive and 2-transitive: Synchronization and its friends
%J EMS surveys in mathematical sciences
%D 2017
%P 101-184
%V 4
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4171/emss/4-2-1/
%R 10.4171/emss/4-2-1
%F 10_4171_emss_4_2_1

Cité par Sources :