Synchronizing Automata and Approaches to the Cerny Conjecture
11/10/2013 Sexta-feira, 11 de Outubro de 2013, 16:00-17:00, IIIUL - Sala B1-01
Emanuele Rodaro (CMUP / FCUP, Portugal)
Instituto para a Investigação Interdisciplinar da Universidade de Lisboa
An automaton is called synchronizing if there is a word w and a state q such that w applied to an arbitrary state p leads to q. This notion naturally appears in different areas of computer science to model systems which are robust against errors. In this seminar we will survey some results on synchronizing automata and different problems related to them, and we will focus in particular on the longstanding Cerny conjecture and some approaches to tackle it.