10 Febbraio, 2009
Sezione di Geometria, Algebra e loro applicazioni
Slowly Synchronizing Automata with Zero and Incomplete Sets
Elena V. Pribavkina, Ural State University - Ekaterinburg - Russia
Aula seminari III piano
Abstract
Using combinatorial properties of incomplete sets in a free monoid we construct a series of $n$-state deterministic automata with zero whose shortest synchronizing word has length
$\frac{n^2}4+\frac{n}2-1$.