2014/04/11 by Robert Brijder, Brijder, Robert
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Advanced Database Systems and Queries #Advanced biosensing and bioanalysis techniques #Computational Complexity (cs.CC) #DNA and Biological Computing #Distributed #Distributed systems and fault tolerance #Electrochemical sensors and biosensors #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1404.3166
openalex publication_date 2014/04/11 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
We study the set of output stable configurations of chemical reaction\ndeciders (CRDs). It turns out that CRDs with only bimolecular reactions (which\nare almost equivalent to population protocols) have a special structure that\nallows for an algorithm to efficiently compute their finite set of minimal\noutput unstable configurations. As a consequence, a relatively large set of\nconfigurations may be efficiently checked for output stability.\n We also provide a number of observations regarding the semilinearity result\nof Angluin et al. [Distrib. Comput., 2007] from the context of population\nprotocols (which is a central result for output stable CRDs). In particular, we\nobserve that the computation-friendly class of totally stable CRDs has equal\nexpressive power as the larger class of output stable CRDs.\n