Blondin, Michael ;
Esparza, Javier ;
Genest, Blaise ;
Helfrich, Martin ;
Jaax, Stefan
Succinct Population Protocols for Presburger Arithmetic
Abstract
In [Dana Angluin et al., 2006], Angluin et al. proved that population protocols compute exactly the predicates definable in Presburger arithmetic (PA), the firstorder theory of addition. As part of this result, they presented a procedure that translates any formula φ of quantifierfree PA with remainder predicates (which has the same expressive power as full PA) into a population protocol with 2^𝒪(poly(φ)) states that computes φ. More precisely, the number of states of the protocol is exponential in both the bit length of the largest coefficient in the formula, and the number of nodes of its syntax tree.
In this paper, we prove that every formula φ of quantifierfree PA with remainder predicates is computable by a leaderless population protocol with 𝒪(poly(φ)) states. Our proof is based on several new constructions, which may be of independent interest. Given a formula φ of quantifierfree PA with remainder predicates, a first construction produces a succinct protocol (with 𝒪(φ³) leaders) that computes φ; this completes the work initiated in [Michael Blondin et al., 2018], where we constructed such protocols for a fragment of PA. For large enough inputs, we can get rid of these leaders. If the input is not large enough, then it is small, and we design another construction producing a succinct protocol with one leader that computes φ. Our last construction gets rid of this leader for small inputs.
BibTeX  Entry
@InProceedings{blondin_et_al:LIPIcs:2020:11901,
author = {Michael Blondin and Javier Esparza and Blaise Genest and Martin Helfrich and Stefan Jaax},
title = {{Succinct Population Protocols for Presburger Arithmetic}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {40:140:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771405},
ISSN = {18688969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11901},
URN = {urn:nbn:de:0030drops119018},
doi = {10.4230/LIPIcs.STACS.2020.40},
annote = {Keywords: Population protocols, Presburger arithmetic, state complexity}
}
04.03.2020
Keywords: 

Population protocols, Presburger arithmetic, state complexity 
Seminar: 

37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Issue date: 

2020 
Date of publication: 

04.03.2020 