| Sunto: |
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.
|