Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-24T02:12:40.007Z Has data issue: false hasContentIssue false
  • English
  • Français

Efficient simulation of synchronous systems by multi-speed systems

Published online by Cambridge University Press:  15 April 2005

Tomasz Jurdziński ,
Mirosław Kutyłowski  and
Jan Zatopiański
Tomasz Jurdziński
Affiliation:
Institute of Computer Science, Wrocław University, Przesmyckiego 20, PL-51-151 Wrocław, Poland. Institute of Mathematics and Computer Science, Kassel University, Heinrich-Plett-Str. 40, D-34132 Kassel, Germany.
Mirosław Kutyłowski
Affiliation:
Institute of Mathematics, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, PL-50-370 Wrocław, Poland.
Jan Zatopiański
Affiliation:
Institute of Mathematics, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, PL-50-370 Wrocław, Poland.
Get access

Abstract

We consider systems consisting of finite automata communicating by exchanging messagesand working on the same read-only data.We investigate the situation in which the automata work with constantbut different speeds. We assume furthermore that the automata are not aware of the speeds andthey 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 whichall automata work with the same speed.

Keywords

Multi-head automatasystems of finite automatacommunication complexitymessage complexity
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 39 , Issue 2 , April 2005 , pp. 403 - 419
Copyright
© EDP Sciences, 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Borodin, A. and Cook, S., A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput. 11 (1982) 287–297. CrossRef
Beame, P., Tompa, M. and Yan, P., Communication-space tradeoffs for unrestricted protocols. SIAM J. Comput. 23 (1994) 652–661. CrossRef
T. Jurdziński and M. Kutyłowski, Communication gap for finite memory devices. Automata, Languages and Programming, in Proc. ICALP'2001. Lect. Notes Comput. Sci. 2076 (2001) 1052–1064.
T. Jurdziński, K. Kutyłowski and K. Loryś, Multi-party finite computations. Computing and Combinatorics, in Proc. COCOON '99. Lect. Notes Comput. Sci. 1627 (1999) 318–329.
T. Jurdziński, M. Kutyłowski, P. Rzechonek and J. Zatopiański, Communication complexity for multi-speed cooperation automata. I Konferencja Młodych Matematyków, Oficyna Wydawnicza Politechniki Wrocławskiej (2001).
T. Jurdziński, M. Kutyłowski and J. Zatopiański, Communication complexity for asynchronous systems of finite devices, in Proc. 15th International Parallel & Distributed Processing Symposium (IPDPS-01), Los Alamitos, CA, April 23–27. IEEE Comput. Soci. (2001) 139.
Mitrana, V. and Martin-Vide, C., Some undecidable problems for parallel communicating finite automata systems. Inform. Proc. Lett. 77 (2001) 239–245.
V. Mitrana, On the degree of communication in parallel communicating finite automata systems. IWDCAGRS: Proc. International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, Otto-von-Guericke Universität (1999) 155–165.
J. Zatopiański, Computational complexity of limited memory systems. Ph.D. Thesis, Institute of Electronics, Wrocław University of Technology, Wrocław (2002).