@inproceedings{7e42ff6d4b5a4688a0290d8af99db92f,
title = "Population protocols on graphs: A hierarchy",
abstract = "Population protocols have been introduced as a model in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. In this paper, we consider population protocols acting on families of graphs, that is to say on particular topologies. Stably computable predicates on strings of size n correspond exactly to languages of NSPACE(n), that is to say to non-deterministic space of Turing machines. Stably computable predicates on cliques correspond to semi-linear predicates, namely exactly those definable in Presburger's arithmetic. Furthermore, we exhibit a strict hierarchy in-between when considering graphs between strings and cliques.",
keywords = "computability, hierarchy, population protocols, space complexity",
author = "Olivier Bournez and Jonas Lef{\`e}vre",
year = "2013",
month = jan,
day = "1",
doi = "10.1007/978-3-642-39074-6\_5",
language = "English",
isbn = "9783642390739",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "31--42",
booktitle = "Unconventional Computation and Natural Computation - 12th International Conference, UCNC 2013, Proceedings",
note = "12th International Conference on Unconventional Computation and Natural Computation, UCNC 2013 ; Conference date: 01-07-2013 Through 05-07-2013",
}