Search Results

Documents authored by Huls, Rachel N.


Document
Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria

Authors: Xiang Huang and Rachel N. Huls

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)


Abstract
Bournez, Fraigniaud, and Koegler [Bournez et al., 2012] defined a number in [0,1] as computable by their Large-Population Protocol (LPP) model, if the proportion of agents in a set of marked states converges to said number over time as the population grows to infinity. The notion, however, restricts the ordinary differential equations (ODEs) associated with an LPP to have only finitely many equilibria. This restriction places an intrinsic limitation on the model. As a result, a number is computable by an LPP if and only if it is algebraic, namely, not a single transcendental number can be computed under this notion. In this paper, we lift the finitary requirement on equilibria. That is, we consider systems with a continuum of equilibria. We show that essentially all numbers in [0,1] that are computable by bounded general-purpose analog computers (GPACs) or chemical reaction networks (CRNs) can also be computed by LPPs under this new definition. This implies a rich series of numbers (e.g., the reciprocal of Euler’s constant, π/4, Euler’s γ, Catalan’s constant, and Dottie number) are all computable by LPPs. Our proof is constructive: We develop an algorithm that transfers bounded GPACs/CRNs into LPPs. Our algorithm also fixes a gap in Bournez et al.’s construction of LPPs designed to compute any arbitrary algebraic number in [0,1].

Cite as

Xiang Huang and Rachel N. Huls. Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.DNA.28.7,
  author =	{Huang, Xiang and Huls, Rachel N.},
  title =	{{Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.28.7},
  URN =		{urn:nbn:de:0030-drops-167922},
  doi =		{10.4230/LIPIcs.DNA.28.7},
  annote =	{Keywords: Population protocols, Chemical reaction networks, Analog computation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail