Population protocols on graphs: a hierarchy

DOI10.1007/978-3-642-39074-6_5zbMATH Open1381.68080OpenAlexW200504655MaRDI QIDQ5300908FDOQ5300908

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

Recommendations

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

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)

Cited In (9)

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

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)