Universidade do Minho  

Mapa do Site
Synchronizing groups and automata

An finite-state automaton is said to be synchronizing if it admits a reset word. Cerny's conjecture, first formulated in 1964, states that if an n-state automaton admits a reset word, then it admits such a word with length at most (n-1)^2. The study of synchronizing automata led to the exploration of several interesting problems in the theory of finite permutation groups. A permutation group G acting on a finite set is said to be non-synchronizing if there is a non-trivial partition P of the underlying set and a transversal S of P such that the images of S under the action of G are all transversals for P. Otherwise G is called synchronising. It is clear that a synchronizing group is transitive and it is primitive. However, the converse of this statement is not true: there are several classes primitive non-synchronizing groups. In this talk I will explain the connection between synchronizing groups and automata, exhibit several classes of primitive non-synchronizing groups, and report on some computer calculations that was aimed at determining the primitive non-synchronising groups of degree up to 100.
  © 2024 Universidade do Minho  - Termos Legais  - actualizado por CMAT Símbolo de Acessibilidade na Web D.