Solving computational learning problems of boolean formulae on DNA computers

Yasubumi Sakakibara

doi:10.1007/3-540-44992-2_15

Solving computational learning problems of boolean formulae on DNA computers

Yasubumi Sakakibara

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

We apply a DNA-based massively parallel exhaustive search to solving the computational learning problems of DNF (disjunctive normal form) Boolean formulae. Learning DNF formulae from examples is one of the most important open problems in computational learning theory and the problem of learning 3-term DNF formulae is known as intractable if RP 6 ≠ NP. We propose new methods to encode any k-term DNF formula to a DNA strand, evaluate the encoded DNF formula for a truth-value assignment by using hybridization and PCR, and find a consistent DNF formula with the given examples. By employing these methods, we show that the class of k-term DNF formulae (for any constant k) and the class of general DNF formulae are eficiently learnable on DNA computer.

Original language	English
Title of host publication	DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers
Editors	Grzegorz Rozenberg, Anne Condon
Publisher	Springer Verlag
Pages	220-230
Number of pages	11
ISBN (Print)	3540420762, 9783540420767
DOIs	https://doi.org/10.1007/3-540-44992-2_15
Publication status	Published - 2001
Externally published	Yes
Event	6th International Workshop on DNA-Based Computers, DNA 2000 - Leiden, Netherlands Duration: 2000 Jun 13 → 2000 Jun 17

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2054
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	6th International Workshop on DNA-Based Computers, DNA 2000
Country/Territory	Netherlands
City	Leiden
Period	00/6/13 → 00/6/17

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-44992-2_15

Cite this

Sakakibara, Y. (2001). Solving computational learning problems of boolean formulae on DNA computers. In G. Rozenberg, & A. Condon (Eds.), DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers (pp. 220-230). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2054). Springer Verlag. https://doi.org/10.1007/3-540-44992-2_15

Solving computational learning problems of boolean formulae on DNA computers. / Sakakibara, Yasubumi.
DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers. ed. / Grzegorz Rozenberg; Anne Condon. Springer Verlag, 2001. p. 220-230 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2054).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sakakibara, Y 2001, Solving computational learning problems of boolean formulae on DNA computers. in G Rozenberg & A Condon (eds), DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2054, Springer Verlag, pp. 220-230, 6th International Workshop on DNA-Based Computers, DNA 2000, Leiden, Netherlands, 00/6/13. https://doi.org/10.1007/3-540-44992-2_15

Sakakibara Y. Solving computational learning problems of boolean formulae on DNA computers. In Rozenberg G, Condon A, editors, DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers. Springer Verlag. 2001. p. 220-230. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44992-2_15

Sakakibara, Yasubumi. / Solving computational learning problems of boolean formulae on DNA computers. DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers. editor / Grzegorz Rozenberg ; Anne Condon. Springer Verlag, 2001. pp. 220-230 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{57c3ba288adb4ec0bc360a6d8ea7ec57,

title = "Solving computational learning problems of boolean formulae on DNA computers",

abstract = "We apply a DNA-based massively parallel exhaustive search to solving the computational learning problems of DNF (disjunctive normal form) Boolean formulae. Learning DNF formulae from examples is one of the most important open problems in computational learning theory and the problem of learning 3-term DNF formulae is known as intractable if RP 6 ≠ NP. We propose new methods to encode any k-term DNF formula to a DNA strand, evaluate the encoded DNF formula for a truth-value assignment by using hybridization and PCR, and find a consistent DNF formula with the given examples. By employing these methods, we show that the class of k-term DNF formulae (for any constant k) and the class of general DNF formulae are eficiently learnable on DNA computer.",

author = "Yasubumi Sakakibara",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001. Copyright: Copyright 2016 Elsevier B.V., All rights reserved.; 6th International Workshop on DNA-Based Computers, DNA 2000 ; Conference date: 13-06-2000 Through 17-06-2000",

year = "2001",

doi = "10.1007/3-540-44992-2_15",

language = "English",

isbn = "3540420762",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "220--230",

editor = "Grzegorz Rozenberg and Anne Condon",

booktitle = "DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers",

}

TY - GEN

T1 - Solving computational learning problems of boolean formulae on DNA computers

AU - Sakakibara, Yasubumi

PY - 2001

Y1 - 2001

N2 - We apply a DNA-based massively parallel exhaustive search to solving the computational learning problems of DNF (disjunctive normal form) Boolean formulae. Learning DNF formulae from examples is one of the most important open problems in computational learning theory and the problem of learning 3-term DNF formulae is known as intractable if RP 6 ≠ NP. We propose new methods to encode any k-term DNF formula to a DNA strand, evaluate the encoded DNF formula for a truth-value assignment by using hybridization and PCR, and find a consistent DNF formula with the given examples. By employing these methods, we show that the class of k-term DNF formulae (for any constant k) and the class of general DNF formulae are eficiently learnable on DNA computer.

AB - We apply a DNA-based massively parallel exhaustive search to solving the computational learning problems of DNF (disjunctive normal form) Boolean formulae. Learning DNF formulae from examples is one of the most important open problems in computational learning theory and the problem of learning 3-term DNF formulae is known as intractable if RP 6 ≠ NP. We propose new methods to encode any k-term DNF formula to a DNA strand, evaluate the encoded DNF formula for a truth-value assignment by using hybridization and PCR, and find a consistent DNF formula with the given examples. By employing these methods, we show that the class of k-term DNF formulae (for any constant k) and the class of general DNF formulae are eficiently learnable on DNA computer.

UR - http://www.scopus.com/inward/record.url?scp=33745749072&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33745749072&partnerID=8YFLogxK

U2 - 10.1007/3-540-44992-2_15

DO - 10.1007/3-540-44992-2_15

M3 - Conference contribution

AN - SCOPUS:33745749072

SN - 3540420762

SN - 9783540420767

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 220

EP - 230

BT - DNA Computing - 6th International Workshop on DNA-Based Computers, DNA 2000 Leiden, The Netherlands, June 13-17, 2000 Revised Papers

A2 - Rozenberg, Grzegorz

A2 - Condon, Anne

PB - Springer Verlag

T2 - 6th International Workshop on DNA-Based Computers, DNA 2000

Y2 - 13 June 2000 through 17 June 2000

ER -

Solving computational learning problems of boolean formulae on DNA computers

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this