EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO-Theor. Inf. Appl.
Volume 39, Number 2, April-June 2005
Page(s) 403 - 419
DOI 10.1051/ita:2005025

Theoret. Informatics Appl. 39, 403-419 (2005)
DOI: 10.1051/ita:2005025

Efficient simulation of synchronous systems by multi-speed systems

Tomasz Jurdzinski1, 2, Miroslaw Kutylowski3 and Jan Zatopianski3

1  Institute of Computer Science, Wroclaw University, Przesmyckiego 20, PL-51-151 Wroclaw, Poland.
2  Institute of Mathematics and Computer Science, Kassel University, Heinrich-Plett-Str. 40, D-34132 Kassel, Germany.
3  Institute of Mathematics, Wroclaw University of Technology, Wybrzeze Wyspianskiego 27, PL-50-370 Wroclaw, Poland.


(Received November, 2002. Accepted September, 2004.)

Abstract
We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is the number of messages sent by the automata. The main result of this paper is that multi-speed systems are as powerful as synchronous systems, in which all automata work with the same speed.


Mathematics Subject Classification. 03D15, 68Q45

Key words: Multi-head automata -- systems of finite automata -- communication complexity -- message complexity


© EDP Sciences 2005


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.