Combinatorical and Algebraic Structures Seminar
Session details
| Date: | 7.5.2013 |
| Speaker: | Alessandra Cherubini, Dipartimento di Matematica, Politecnico di Milano |
| Title: | Around Cerny's conjecture: synchronizing and collapsing words |
| Abstract: | A word w over a finite alphabet $\Sigma$ is called $k$-collapsing, with $k$ positive integer, if for each finite deterministic automaton $A=(Q,\Sigma,\delta)$ the inequality $|\delta(Q,w)|\leq|Q|-k$ holds provided that $|\delta(Q,v)|\leq|Q|- k$ for some word $v$, depending on $A$. A word over the alphabet $\Sigma$ is called $k$-synchronizing if it is a reset word for all synchronizing automata with $k+1$ states on the alphabet $\Sigma$. These notions naturally arise from the well-known Cerny's conjecture, one of the oldest open problems in the theory of finite automata; however they were introduced under different names in different frameworks. In this talk the motivations of the interest of such words, some results in this area and some open problem will be presented. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož