www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/18446

Title: Output Stability and Semilinear Sets in Chemical Reaction Networks and Deciders
Authors: BRIJDER, Robert
Issue Date: 2014
Publisher: Springer
Citation: Murata, Satoshi; Kobayashi, Satoshi (Ed.). DNA Computing and Molecular Programming, p. 100-113
Series/Report: Lecture Notes in Computer Science
Series/Report no.: 8727
Abstract: We study the set of output stable configurations of chemical reaction deciders (CRDs). It turns out that CRDs with only bimolecular reactions (which are almost equivalent to population protocols) have a special structure that allows for an algorithm to efficiently calculate the (finite) set of minimal output stable configurations. As a consequence, a relatively large sequence of configurations may be efficiently checked for output stability. We also provide a number of observations regarding the semilinearity result of Angluin et al. [Distrib. Comput., 2007] from the context of population protocols (which is a central result for output stable CRDs). In particular, we observe that the computation-friendly class of totally stable CRDs has equal expressive power as the larger class of output stable CRDs.
URI: http://hdl.handle.net/1942/18446
DOI: 10.1007/978-3-319-11295-4_7
ISBN: 978-3-319-11294-7
ISSN: 0302-9743
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Main article181.42 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.