Home   /   Research   /  Events
Search by section
Search string Reset
 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$.