Error-resilient DNA computation.

Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101766
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:05:41 AM
Last modification on : Thursday, May 23, 2019 - 1:28:22 AM

File

RR1995-20.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101766, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

16

Files downloads

44