Error-resilient DNA computation. - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1995

Error-resilient DNA computation.

(1) , (1) , (1)
1

Résumé

The DNA model of computation, with test tubes of DNA molecules encoding bit sequences, is based on three primitives, extract-a-bit, merge-two-tubes and detect-emptiness. Perfect operations can test the satisfiability of any boolean formula in linear time. However, in reality the extract operation is faulty. We determine the minimum number of faulty extract operations required to simulate a single highly reliable extract operation, and derive a method for converting any algorithm based on error-free operations to an error-resilient one.
Le modèle de calcul basé sur les molécules d'ADN codant des suites de bits utilise trois primitives, extraction d'un bit, fusion de deux éprouvettes et détection d'éprouvette vide. Avec des opérations fiables, on peut tester la satisfiabilité d'une formule booléenne quelconque en temps linéaire. Mais en réalité, l'opération d'extractions est peu fiable. Nous déterminons le nombre minimum d'extractions non fiables et de fusions permettant de simuler une extraction très fiable, puis donnons une réduction qui, d'un algorithme basé sur des primitives parfaitement fiables, déduit un algorithme lorsque l'opération extraction est non fiable.
Fichier principal
Vignette du fichier
RR1995-20.pdf (265.28 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101766 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101766 , version 1

Citer

Richard M. Karp, Claire Kenyon, Orli Waarts. Error-resilient DNA computation.. [Research Report] LIP RR-1995-20, Laboratoire de l'informatique du parallélisme. 1995, 2+23p. ⟨hal-02101766⟩
17 Consultations
93 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More