nach oben

Natural Computing

Erschienen in:

01.06.2016

Minimal output unstable configurations in chemical reaction networks and deciders

verfasst von: Robert Brijder

Erschienen in: Natural Computing | Ausgabe 2/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 compute their finite set of minimal output unstable configurations. As a consequence, a relatively large set 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 20(4):279–304, 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.

Vorheriger Artikel On decidability and closure properties of language classes with respect to bio-operations

Nächster Artikel Probability 1 computation with chemical reaction networks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Angluin D, Aspnes J, Diamadi Z, Fischer MJ, Peralta R (2006) Computation in networks of passively mobile finite-state sensors. Distrib Comput 18(4):235–253CrossRefMATH

Angluin D, Aspnes J, Eisenstat D (2006) Stably computable predicates are semilinear. In: Ruppert E, Malkhi D (eds) Proceedings of the 25th annual ACM symposium on principles of distributed computing (PODC 2006). ACM, pp 292–299

Angluin D, Aspnes J, Eisenstat D, Ruppert E (2007) The computational power of population protocols. Distrib Comput 20(4):279–304CrossRefMATH

Aspnes J, Ruppert E (2007) An introduction to population protocols. Bull EATCS 93:98–117MathSciNetMATH

Brijder R (2014) Output stability and semilinear sets in chemical reaction networks and deciders. In: Murata S, Kobayashi S (eds) Proceedings of the 20th international conference on DNA computing and molecular programming (DNA 20), volume 8727 of lecture notes in computer science. Springer, pp 100–113

Chen H-L, Doty D, Soloveichik D (2012) Deterministic function computation with chemical reaction networks. In: Stefanovic D, Turberfield AJ (eds) Proceedings of the 18th international conference on DNA computing and molecular programming (DNA 18), volume 7433 of lecture notes in computer science. Springer, pp 25–42

Chen H-L, Doty D, Soloveichik D (2014) Rate-independent computation in continuous chemical reaction networks. In: Naor M (ed) Innovations in theoretical computer science (ITCS’14). ACM, pp 313–326

Cook M, Soloveichik D, Winfree E, Bruck J (2009) Programmability of chemical reaction networks. In: Condon A, Harel D, Kok JN, Salomaa A, Winfree E (eds) Algorithmic bioprocesses, natural computing series. Springer, Berlin, pp 543–584CrossRef

Dickson LE (1913) Finiteness of the odd perfect and primitive abundant numbers with \(n\) distinct prime factors. Am J Math 35:413–422MathSciNetCrossRefMATH

Doty D (2014) Timing in chemical reaction networks. In: Chekuri C (ed) Proceedings of the 25th annual ACM–SIAM symposium on discrete algorithms (SODA 2014). SIAM, pp 772–784

Doty D, Hajiaghayi M (2013) Leaderless deterministic chemical reaction networks. In: Soloveichik D, Yurke B (eds) Proceedings of the 19th international conference on DNA computing and molecular programming (DNA 19), volume 8141 of lecture notes in computer science. Springer, pp 46–60

Karp RM, Miller RE (1969) Parallel program schemata. J Comput Syst Sci 3(2):147–195MathSciNetCrossRefMATH

Leroux J (2012) Vector addition systems reachability problem (a simpler solution). In: Voronkov A (ed) Proceedings of the Alan Turing centenary conference (Turing-100), volume 10 of EPiC series, pp 214–228

Mayr EW (1981) An algorithm for the general Petri net reachability problem. In: Proceedings of the 13th annual ACM symposium on theory of computing (STOC ’81). ACM, New York, NY, USA, pp 238–246

Peterson JL (1977) Petri nets. ACM Comput Surv 9(3):223–252CrossRefMATH

Plotkin GD (2013) A calculus of chemical systems. In: Tannen V, Wong L, Libkin L, Fan W, Tan W-C, Fourman M (eds) In search of elegance in the theory and practice of computation, volume 8000 of lecture notes in computer science. Springer, Berlin, Heidelberg, pp 445–465

Soloveichik D, Cook M, Winfree E, Bruck J (2008) Computation with finite stochastic chemical reaction networks. Nat Comput 7(4):615–633MathSciNetCrossRefMATH

Soloveichik D, Seelig G, Winfree E (2010) DNA as a universal substrate for chemical kinetics. Proc Natl Acad Sci 107(12):5393–5398CrossRef

Stanley RP (2011) Enumerative combinatorics. Cambridge studies in advanced mathematics, vol 1, 2nd edn. Cambridge University Press, CambridgeCrossRef

Willard DE (1985) New data structures for orthogonal range queries. SIAM J Comput 14(1):232–253MathSciNetCrossRefMATH

Yamasaki H (1981) On weak persistency of Petri nets. Inf Process Lett 13(3):94–97MathSciNetCrossRefMATH

Titel: Minimal output unstable configurations in chemical reaction networks and deciders
verfasst von: Robert Brijder
Publikationsdatum: 01.06.2016
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 2/2016
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-015-9506-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2016

Physarum in silicon: the Greek motorways study

Classical, quantum and biological randomness as relative unpredictability

Emulating cellular automata in chemical reaction–diffusion networks

Development of firefly algorithm via chaotic sequence and population diversity to enhance the image contrast

Probability 1 computation with chemical reaction networks

On decidability and closure properties of language classes with respect to bio-operations

Premium Partner