Algebra and Logic Seminar - 7/10/2015

Wednesday, 7 October 2015, 2:00 p.m.

Lecturer: (i) António Malheiro e (ii) Jorge Orestes Cerdeira (CMA e DM, FCT-UNL)

Title: "Sobre autómatos sincronizantes"

Local: Sala de Seminários, Edifício VII

Faculdade de Ciências e Tecnologia, Quinta da Torre, Caparica

Abstract: (i) Começa por se apresentar os conceitos básicos sobre autómatos sincronizantes e introduz-se a conjetura de Cerný, que estabelece um limite superior para a palavra de comprimento mínimo (relativa ao número de estados do autómato) que restabelece o autómato. (ii) Em seguida analisa-se a dificuldade de encontrar palavras de comprimento mínimo que restabelecem o autómato, propõe-se um enunciado alternativo da conjetura de Cerný em termos de um modelo compacto em variáveis 0/1, e discute-se algumas consequências decorrentes do modelo proposto.