Centro de
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 \v{C}ern\'y conjecture, one of the oldest and most famous problems in automata theory, according to which a synchronizing nn-state automaton has a reset word of length at most (n1)2(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 GG on a set Ω\Omega is said to synchronize a map ff if the monoid G,f\langle G,f\rangle generated by GG and ff is synchronizing in the above sense; we say GG 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 22-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 \v{C}ern\'y 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 \v{C}ern\'y conjecture, some challenges to finite geometers, some thoughts about infinite analogues, and a long list of open problems.
A semigroup is \emph{nilpotent} of degree 3 if it has a zero, every product of 3 elements equals the zero, and some product of 2 elements is non-zero. It is part of the folklore of semigroup theory that almost all finite semigroups are nilpotent of degree 3. We give formulae for the number of nilpotent semigroups of degree 3 with nNn\in\N elements up to equality, isomorphism, and isomorphism or anti-isomorphism. Likewise, we give formulae for the number of nilpotent commutative semigroups with nn elements up to equality and up to isomorphism.
There are no more papers matching your filters at the moment.