Rapport de Recherche Litp /
Litp research reports
6 pages - Mai/May 1995 - Document en anglais.
PostScript : Ko /Kb
Titre / Title: A QUASI-OPTIMAL TIME FOR SYNCHRONIZING TWO INTERACTING FINITE AUTOMATA
Abstract : Mazoyer has constructed a family (Am)meN of systems of two interacting 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.
Publications internes Litp 1995 / Litp research reports 1995