H.Vivien
A QUASI-OPTIMAL TIME FOR SYNCHRONIZING TWO INTERACTING FINITE AUTOMATA

 Mazoyer a construit une famille (Am)meN  de systèmes de deux au­
tomates finis interactifs qui synchronisent en temps à  peu  près
[2/log(m)]Dlog(D)   où  D  désigne le délai de communication.Nous
démontrons ici que les solutions de Mazoyer  sont  optimales  aux
sens suivants:  1°) tout système qui synchronise le fait en temps
au moins [1/log(N)] Dlog(D/2) ,où N est le nombre d'états, si bi­
en  que  l'ordre Dlog(D) est optimal   2°)  les systèmes à la Ma­
zoyer ont environ am3 états , 2/log(m) vaut donc à  peu  près   6
,si bien que les solutions de Mazoyer ont un temps de  synchroni­
sation égal à environ 6  fois  la  borne  inférieure  précédente,
presque optimal donc.
 Mazoyer has constructed a family  (Am)meN  of systems of two in­
teracting  finite  automata  which  synchronize  in  time   about
[2/log(m)]  Dlog(D)   where D  is the delay of communication.Here
we prove that  Mazoyer's solutions are optimal in  the  following
senses:  1°)  any  synchronizing system operates in time at least
[1/log(N)] Dlog(D/2) , N being the number of states, so that  the
order  Dlog(D)  is optimal   2°)  Mazoyer-like systems have about
am3 states so that 2/log(m) is about 6 ,and  Mazoyer's  solutions
have  synchronizing  time   about  6 times the above lower bound,
which is thus nearly optimal.