Population protocols on graphs: a hierarchy

DOI10.1007/978-3-642-39074-6_5MaRDI QIDQ5300908zbMATHOpenAlexFDO

Authors Jonas Lefèvre, Olivier Bournez

Publication date 28 June 2013

Published in Unconventional Computation and Natural Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-39074-6_5

zbMATH Keywords

hierarchypopulation protocolsspace complexitycomputability

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Network protocols (68M12)

Recommendations

• The computational power of population protocols
• Stably computable predicates are semilinear
• Mediated population protocols
• Homonym population protocols
• Mediated Population Protocols

Cited in

(9)

• Large flocks of small birds: on the minimal size of population protocols
• All symmetric predicates in NSPACE\((n^{2})\) are stably computable by the mediated population protocol model
• Mediated population protocols
• The computational power of population protocols
• On the convergence of population protocols when population goes to infinity
• Mediated Population Protocols
• Homonym population protocols
• Brief Announcement: Fast Graphical Population Protocols
• Stably computable predicates are semilinear

This page was built for publication: Population protocols on graphs: a hierarchy

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