All symmetric predicates in NSPACE(n^2) are stably computable by the mediated population protocol model

DOI10.1007/978-3-642-15155-2_25zbMATH Open1287.68015DBLPconf/mfcs/ChatzigiannakisMNPS10OpenAlexW1494218382WikidataQ57608067 ScholiaQ57608067MaRDI QIDQ3586090FDOQ3586090

Authors: Ioannis Chatzigiannakis, Othon Michail, Stavros Nikolaou, Andreas Pavlogiannis, P. G. Spirakis 

Publication date: 3 September 2010

Published in: Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15155-2_25

Recommendations

• Mediated population protocols
• Mediated Population Protocols
• Stably computable predicates are semilinear
• The computational power of population protocols
• Population protocols on graphs: a hierarchy

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Network protocols (68M12)

Cited In (8)

• The computational power of simple protocols for self-awareness on graphs
• Computational models for networks of tiny artifacts: a survey
• Passively mobile communicating machines that use restricted space
• Fault-tolerant simulation of population protocols
• Stably computable predicates are semilinear
• Mediated population protocols
• Population protocols with faulty interactions: the impact of a leader
• Clocked population protocols

This page was built for publication: All symmetric predicates in NSPACE\((n^{2})\) are stably computable by the mediated population protocol model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586090)