Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.06.2015 | Ausgabe 2/2015

Natural Computing 2/2015

Leaderless deterministic chemical reaction networks

Zeitschrift:
Natural Computing > Ausgabe 2/2015
Autoren:
David Doty, Monir Hajiaghayi

Abstract

This paper answers an open question of  Chen et al. (DNA 2012: proceedings of the 18th international meeting on DNA computing and molecular programming, vol 7433 of lecture notes in computer science. Springer, Berlin, pp 25–42, 2012), who showed that a function \(f:\mathbb {N}^k\rightarrow \mathbb {N}^l\) is deterministically computable by a stochastic chemical reaction network (CRN) if and only if the graph of \(f\) is a semilinear subset of \(\mathbb {N}^{k+l}\). That construction crucially used “leaders”: the ability to start in an initial configuration with constant but non-zero counts of species other than the \(k\) species \(X_1,\ldots ,X_k\) representing the input to the function \(f\). The authors asked whether deterministic CRNs without a leader retain the same power. We answer this question affirmatively, showing that every semilinear function is deterministically computable by a CRN whose initial configuration contains only the input species \(X_1,\ldots ,X_k\), and zero counts of every other species, so long as \(f({\bf 0})={\bf 0}\). We show that this CRN completes in expected time \(O(n)\), where \(n\) is the total number of input molecules. This time bound is slower than the \(O(\log ^5 n)\) achieved in Chen et al. (2012), but faster than the \(O(n \log n)\) achieved by the direct construction of Chen et al. (2012).

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe​​​​​​​




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 2/2015

Natural Computing 2/2015 Zur Ausgabe

Premium Partner

    Bildnachweise