Efficient simulation of synchronous automata by multi-speed systems
Tomasz Judrdzinski, Miroslaw Kutylowski, Jan Zatopianski
We consider systems consisting of finite automata communicating by
exchanging messages. We investigate the situation in which automata work
with constant but different speeds. We assume furthermore that these
speeds are unknown to the devices and cannot be measured directly. In
particular, it may happen that some speed cannot be expressed exactly by
the means of internal states of automata. Nevertheless, automata have to
compute the correct output. We call this model multi-speed systems of
finite automata}.
The main result of this paper is that multi-speed systems are as
powerful as synchronous systems, where all automata work with the same
speed.