A QUASI-OPTIMAL TIME FOR SYNCHRONIZING TWO INTERACTING FINITE AUTOMATA

H.Vivien

IBP-Litp 1995/21: 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

Résumé : Mazoyer a construit une famille (Am)meN de systèmes de deux automates 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 bien que l'ordre Dlog(D) est optimal 2°) les systèmes à la Mazoyer ont environ am3 états , 2/log(m) vaut donc à peu près 6 ,si bien que les solutions de Mazoyer ont un temps de synchronisation égal à environ 6 fois la borne inférieure précédente, presque optimal donc.

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