Alternatívna charakterizácia synchronizovaného alternovania

0405550 - UIVT-O 330929 RIV SK slo C - Konferenční příspěvek (zahraniční konf.)
Pardubská, D. - Wiedermann, Jiří
Alternatívna charakterizácia synchronizovaného alternovania.
[An Alternate Characterization of Synchronized Alternation.]
ITAT 2005. Information Technologies - Applications and Theory. Košice: Prírodovedecká fakulta, Univerzita P. J. Šafárika, 2005 - (Vojtáš, P.), s. 133-144. ISBN 80-7097-609-8.
[ITAT 2005. Račkova dolina (SK), 20.09.2005-25.09.2005]
Grant CEP: GA AV ČR 1ET100300517
Grant ostatní: grant(EU) APVT-20-018902
Výzkumný záměr: CEZ:AV0Z10300504
Klíčová slova: alternation * wireless networks * mobile computing * Turing machines * complexity
Kód oboru RIV: BA - Obecná matematika

V článku navrhneme nový výpočtový model, ktorého návrh je inšpirovaný základnými vlastnosťami bezdrôtových mobilných komunikačných sieťach. V podstate ide o deterministický Turingov stroj obohatený o možnosť vytvárania nových komunikujúcich procesov, pritom bezdrôtová komunikácia medzi procesmi prebieha prostredníctvom explicitne určených kanálov. Dokážeme, že výpočtovo sú tieto stroje časovo aj priestorovo ekvivalentné synchronizovaným alternujúcim Turingovým strojom. To ukazuje, že synchronizované alternovanie možno nahradiť deterministickým paralelizmom s možnosťou neobmedzenej komunikácie a naopak.

A computational model reflecting fundamental computational aspects of wirelessly communicating mobile processors is presented. In essence, our model is a deterministic Turing machine which is able to 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. This shows that nondeterminism can be completely eliminated from synchronized alternation at the price of introducing a program - driven communication among the respective processors.

V článku navrhneme nový výpočetní model, jehož návrh je inspirovaný základními vlastnostmi bezdrátových mobilních komunikačních sítí. V podstatě jde o deterministický Turingův stroj obohacený o možnost vytváření nových komunikujících procesů, přitom bezdrátová komunikace mezi procesy probíhá prostředníctvím explicitně určených kanálů. Dokážeme, že výpočetně jsou tyto stroje časově i prostorově ekvivalentní synchronizovaným alternujícím Turingovým strojům. To ukazuje, že synchronizované alternování lze nahradit deterministickým paralelizmem s možností neomezené komunikace a naopak.
Trvalý link: http://hdl.handle.net/11104/0125706