Horn Clause Computation with DNA Molecules

Satoshi Kobayashi ()
Additional contact information
Satoshi Kobayashi: Tokyo Denki University

Journal of Combinatorial Optimization, 1999, vol. 3, issue 2, No 8, 277-299

Abstract: Abstract In this paper, we will propose Horn clause computation as an underlying computational framework of DNA computer. Horn clause program is a subclass of the formulas of first order logic and has close relation to PROLOG language. The computational power of Horn clauses was discussed in (Tärnland, 1977) and it was shown that a finite set of Horn clauses is computationally equivalent to Turing Machine. Furthermore, it should be noted that Horn programs are adequate for representing nondeterministic computation. Thus, its parallel implementation with huge number of molecules might have possibility to overcome the computational power of conventional computers. It should also be noted that the clear logical semantics of Horn programs might enable us to accept it as a higher-level programming language of DNA computer. The aim of this paper is to propose an experimental method for implementing deduction with a subclass of Horn programs, called simple Horn programs. The computational power of this model is theoretically investigated and demonstrated with some applications to NP-complete problems.

Keywords: DNA computing; Horn clauses; NP-complete problems (search for similar items in EconPapers)
Date: 1999
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009893911892 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:3:y:1999:i:2:d:10.1023_a:1009893911892

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009893911892

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().