Type of publication: | Inproceedings |
Entered by: | |
Title | All Symmetric Predicates in NSPACE(n^2) are Stably Computable by the Mediated Population Protocol Model |
Bibtex cite ID | RACTI-RU1-2010-7 |
Booktitle | 35th International Symposium on Mathematical Foundations of Computer Science (MFCS) |
Series | Lecture Notes in Computer Science |
Year published | 2010 |
Month | August |
Publisher | Springer-Verlag Berlin Heidelberg |
Location | Brno, Czech Republic |
URL | http://mfcsl2010.fi.muni.cz/mfcs |
Keywords | population protocols,mediated population protocols,diffuse computation,passive mobility,wireless sensor networks,stable computation |
Abstract | This work focuses on the computational power of the Mediated Population Protocol model on complete communication graphs and initially identical edges (SMPP). In particular, we investigate the class MPS of all predicates that are stably computable by the SMPP model. It is already known that MPS is in the symmetric subclass of NSPACE(n^2). Here we prove that this inclusion holds with equality, thus, providing the following exact characterization for MPS: A predicate is in MPS iff it is symmetric and is in NSPACE(n^2). |
Authors | |
Topics
| |
BibTeX | BibTeX |
RIS | RIS |
Attachments |
mfcs10 - proceedings - CMNPS.pdf (main file) |
mfcs10 - TechReport - CMNPS.pdf |
|
Publication ID | 733 |