Observatorio de I+D+i UPM

Memorias de investigación
Ponencias en congresos:
Autonomous Resolution Based on DNA Strand Displacement
Año:2011
Áreas de investigación
  • Biocomputación,
  • Ciencias de la computación y tecnología informática
Datos
Descripción
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 enzyme-free 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.
Internacional
Si
Nombre congreso
International 717th Conference on DNA Computing and Molecular Programming
Tipo de participación
960
Lugar del congreso
Pasadena, California, USA
Revisores
Si
ISBN o ISSN
978-3-642-23637-2
DOI
10.1007/978-3-642-23638-9_16
Fecha inicio congreso
19/09/2011
Fecha fin congreso
23/09/2011
Desde la página
190
Hasta la página
203
Título de las actas
DNA COMPUTING AND MOLECULAR PROGRAMMING Lecture Notes in Computer Science, 2011, Volume 6937/2011, 190-203, DOI: 10.1007/978-3-642-23638-9_16
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Alfonso Vicente Rodriguez-Paton Aradas (UPM)
  • Autor: Iñaki Sainz de Murieta Fuentes (UPM)
  • Autor: Petr Sosik (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Grupo de Inteligencia Artificial (LIA)
  • Departamento: Inteligencia Artificial
S2i 2021 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)