Error-resilient DNA computation.
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...