New Computational Paradigms. Changing Conceptions of What is Computable

0306273 - ÚI 2008 RIV DE eng M - Část monografie knihy
Wiedermann, Jiří - Pardubská, D.
On the Power of Broadcasting in Mobile Computing.
[Výpočetní síla vysílání v mobilních výpočtech.]
New Computational Paradigms. Changing Conceptions of What is Computable. Berlin: Springer, 2008 - (Cooper, B.; Löwe, B.; Sorbi, A.), s. 195-209. ISBN 978-0-387-36033-1
Grant CEP: GA AV ČR 1ET100300517
Grant ostatní: VEGA(SK) 1/3106/06
Výzkumný záměr: CEZ:AV0Z10300504
Klíčová slova: wireless Turing machine * alternating Turing machine * broadcasting * mobile computing * complexity
Kód oboru RIV: IN - Informatika

A computational model reflecting fundamental computational aspects of wirelessly communicating mobile processors is presented. In essence, our model is a deterministic Turing machine that can launch new processes among which a wireless communication via explicitly assigned channels must be programmed. We show that computations of such machines are polynomially time- and space-equivalent to the synchronized alternating Turing machines studied previously in the literature.

Je navržen výpočetní model reflektující fundamentální vlastnosti bezdrátově komunikujících procesorů. V podstatě se jedná o deterministický Turingův stroj, který je schopen iniciovat další procesy, které mezi sebou bezdrátové komunikují pomocí explicitně přiřazených kanálů. Ukážeme, že výpočty takového zařízení jsou časově a prostorově polynomicky ekvivalentní výpočtům alternujících Turingových strojů.
Trvalý link: http://hdl.handle.net/11104/0159347