Paper Info
Title
Autonomous resolution based on DNA strand displacement
Abstract
We present a computing model based on the technique of DNA strand displacement which performs a chain of logical resolutions with logical formulae in conjunctive normal form. The model is enzymefree and autonomous. Each clause of a formula is encoded in a separate DNA molecule: propositions are encoded assigning a strand to each proposition p, and its complementary strand to the proposition ¬p; clauses are encoded comprising different propositions in the same strand. The model allows to run logic programs composed of Horn clauses by cascading resolution steps and, therefore, possibly function as an autonomous programmable nano-device. This technique can be also used to solve SAT. The resulting SAT algorithm has a linear time complexity in the number of resolution steps, whereas its spatial complexity is exponential in the number of variables of the formula.
Year
DOI
Venue
2011
10.1007/978-3-642-23638-9_16
DNA
Keywords
Field
DocType
logical resolution,sat algorithm,logical formula,cascading resolution step,different proposition,autonomous programmable nano-device,complementary strand,computing model,linear time complexity,autonomous resolution,dna strand displacement
Dna strand displacement,Proposition,Horn clause,Exponential function,Algorithm,DNA,Conjunctive normal form,Spatial complexity,Time complexity,Mathematics
Conference
Volume
ISSN
Citations 
6937
0302-9743
2
PageRank 
References 
Authors
0.41
15
3
Name
Order
Citations
PageRank
Alfonso Rodríguez-Patón143551.44
Iñaki Sainz de Murieta271.78
Petr Sosík347968.66