La Congettura di Cerny

Lo scopo di questo seminario e' quello di presentare una survey, di natura
introduttiva, su di una ben nota congettura di Informatica teorica riguardante
gli automi sincronizzanti. Un automa deterministico si dice sincronizzante se
esistono una parola w sul suo alfabeto di ingresso ed un suo stato q tali che,
comunque si consideri uno stato p dell'automa, lo stato da esso raggiunto,
leggendo la parola w, a partire da p, e' lo stato q.
La parola w e lo stato q sono detti rispettivamente parola e stato di reset.
Una famosa congettura formulata da Cerny nella seconda meta' degli Anni 60
stabilisce che ogni automa sincronizzante avente n stati possiede una parola
di reset di lunghezza inferiore o uguale a (n-1)^{2}. In questo seminario,
dopo aver delineato il quadro storico e le motivazioni che rendono
significativo lo studio del problema, presenteremo alcune famiglie notevoli di
automi sincronizzanti ed alcune idee soggiacenti alle tecniche utilizzate per
tale
studio.