Alternatívna charakterizácia synchronizovaného alternovania

0405550 - UIVT-O 330929 RIV SK slo C - Conference Paper (international conference)
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]
R&D Projects: GA AV ČR 1ET100300517
Grant - others:grant(EU) APVT-20-018902
Institutional research plan: CEZ:AV0Z10300504
Keywords : alternation * wireless networks * mobile computing * Turing machines * complexity
Subject RIV: BA - General Mathematics

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.
Permanent Link: http://hdl.handle.net/11104/0125706