Usando as ruas da cidade do Porto, construo um grafo dirigido, no qual pretendo colorir as arestas de forma a obter um autómato sincronizável. Isto é, quero pintar as ruas de forma a poder dar um conjunto de indicações para chegar a minha casa, que não dependa do ponto de partida. Será que é possível? Esta questão permaneceu aberta durante quase 40 anos, recentemente Avraham Trahtman encontrou a solução. Outro problema relacionado com este é a conjectura de Černý, que foi proposta em 1964 e continua aberta. Desta vez, o objectivo é limitar o tamanho da sequência de cores necessária para que toda a gente chegue ao mesmo ponto. Podemos ainda questionarmos sobre o tamanho de uma instrução que reuna toda a gente independentemente do ponto de partida e da coloração inicial das ruas. Neste seminário vamos ver um pouco sobre todos estes problemas e alguns dos avanços que têm sido feitos em cada um deles.