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

DOI10.1007/978-3-642-15155-2_25MaRDI QIDQ3586090zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

Recommendations

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

Cited in

(7)

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

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)