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(n2). 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(n2).
All symmetric predicates in NSPACE(n2) are stably computable by the mediated population protocol model / CHATZIGIANNAKIS, IOANNIS; Michail, O.; Nikolaou, S.; Pavlogiannis, A.; Spirakis, P. G.. - STAMPA. - 6281 LNCS:(2010), pp. 270-281. (Intervento presentato al convegno 35th International Symposium on Mathematical Foundations of Computer Science tenutosi a Brno; Czech Republic) [10.1007/978-3-642-15155-2_25].
All symmetric predicates in NSPACE(n2) are stably computable by the mediated population protocol model
CHATZIGIANNAKIS, IOANNIS;
2010
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(n2). 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(n2).| File | Dimensione | Formato | |
|---|---|---|---|
|
Chatzigiannakis_Symmetric_2010.pdf
solo gestori archivio
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
1.2 MB
Formato
Adobe PDF
|
1.2 MB | Adobe PDF | Contatta l'autore |
|
VE_2010_11573-914377.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
1.2 MB
Formato
Adobe PDF
|
1.2 MB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
