DETERMINISTIC SYNCHRONIZATION OF BOUNDED- DELAY AUTOMATA

Authors
FROUGNY C SAKAROVITCH J
Citation
C. Frougny et J. Sakarovitch, DETERMINISTIC SYNCHRONIZATION OF BOUNDED- DELAY AUTOMATA, Theoretical computer science, 191(1-2), 1998, pp. 61-77
Citations number
15
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
191
Issue
1-2
Year of publication
1998
Pages
61 - 77
Database
ISI
SICI code
0304-3975(1998)191:1-2<61:DSOBDA>2.0.ZU;2-T
Abstract
It is shown that a subsequential automaton (i.e. an automaton determin istic with respect to the input) with bounded delay is equivalent to a n on-line automaton, that is an automaton which is letter-to-letter af ter an initial period where it reads the input and output nothing, and subsequential. The results on the synchronisation of automaton with b ounded delay established so far did not keep the property of being sub sequential.