La congettura di Cerny

Lo scopo di questo seminario è 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, è 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 metà 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.