Non-deterministic Population Protocols

Autor:	Laurent Rosaz, Janna Burman, Joffroy Beauquier, Brigitte Rozoy
Rok vydání:	2012
Předmět:	education.field_of_study Theoretical computer science Property (philosophy) Transformation (function) Computer science Population Mobile agent Population protocol education Algorithm Presburger arithmetic
Zdroj:	Lecture Notes in Computer Science ISBN: 9783642354755 OPODIS
DOI:	10.1007/978-3-642-35476-2_5
Popis:	In this paper we show that, in terms of generated output languages, non-deterministic population protocols are strictly more powerful than deterministic ones. Analyzing the reason for this negative result, we propose two slightly enhanced models, in which non-deterministic population protocols can be exactly simulated by deterministic ones. First, we consider a model in which interactions are not only between couples of agents, but also between triples and in which non-uniform initial states are allowed. We generalize this transformation and we prove a general property for a model with interactions between any number of agents. Second, we simulate any non-deterministic population protocol by a deterministic one in a model where a configuration can have an empty output.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::f2fe6e055738cb28089f7cf7bfbe00b7 https://doi.org/10.1007/978-3-642-35476-2_5 Zobrazit plný text záznamu