Synchronisation Déterministe des Automates à délai Borné

C. FROUGNY, J. SAKAROVITCH

IBP-Litp 1995/60: Rapport de Recherche Litp / Litp research reports
18 pages - Janvier/January 1996 - French document.

PostScript : Ko /Kb

Titre / Title: Synchronisation Déterministe des Automates à délai Borné

Résumé : Nous montrons qu'un automate à délai borné sous-séquentiel (i.e. déterministe sur les entrées) est équivalent à un automate en-ligne, c'est-à-dire lettre-à-lettre après une période transitoire fixe où l'automate lit le début de l'entrée sans rien sortir, et sous-séquentiel. Les résultats de synchronisation établis antérieurement pour les automates à délai borné ne préservaient pas la sous-séquentialité.

Abstract : It is shown that a subsequential automaton (i.e. an automaton deterministic with respect to the input) with bounded delay is equivalent to an on-line automaton, that is an automaton which is letter-to-letter after an initial period where it reads the input and output nothing, and subsequential . The results on the synchronisation of automaton with bounded delay established so far did not keep the property of being subsequential.

Publications internes Litp 1995 / Litp research reports 1995