Communication complexity for multi-speed cooperating automata

• Autorzy: Jurdziński T. , Kutyłowski M. , Rzechonek P. , Zatopiański J.
• Konferencja: I konferencja dla Młodych Matematyków Zastosowanie Matematyki - Karpacz 2000
• Języki publikacji: EN

Abstrakty

EN

We consider bounded memory asynchronous systems. They consist of finite automata working independently and communicating by exchanging messages. We discuss what impact the differences in timing models on computational power of such systems have. It is known that a total lack of synchronization has profound consequences for computational power of systems of automata. Lower bounds found for this model indicate that the only way to perform a nontrivial computation would be to re-synchronize the automata every 0(1) steps. We examine much weaker form of asynchronism. We consider the model in which automata work with constant speeds, but the speed might be different for each automaton, and the automata have no knowledge about the speeds. (We call this model multi-speed systems of finite automata.) In particular, it may happen that some speed cannot be expressed exactly by the means of internal states of automata. Nevertheless, we expect the automata to compute the correct output. The main result of this paper is that, quite unexpectedly, the systems described might be as powerful as synchronous systems, where all automata work with the same speed. More precisely, some languages, which have been candidates for distinguishing multi-speed and synchronous models, can be recognized by multi-speed systems with approximately the same number of messages sent.

Słowa kluczowe

EN

communication complexity; finite automata; asynchronous systems

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Prace Naukowe Instytutu Matematyki Politechniki Wrocławskiej. Konferencje
• Rocznik: 2001
• Tom: Vol. 24, nr 3
• Strony: 17--30
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Jurdziński T.

autor

Kutyłowski M.

autor

Rzechonek P.

autor

Zatopiański J.

• Department of Computer Science, technical University of Chemists, Germany.