Solving computational learning problems of Boolean formulae on DNA computers View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001-04-25

AUTHORS

Yasubumi Sakakibara

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 ≠ 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 efficiently learnable on DNA computer. More... »

PAGES

220-230

References to SciGraph publications

Book

TITLE

DNA Computing

ISBN

978-3-540-42076-7
978-3-540-44992-8

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44992-2_15

DOI

http://dx.doi.org/10.1007/3-540-44992-2_15

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1017930394


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Tokyo Denki University", 
          "id": "https://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Information Sciences, Tokyo Denki University, 350-0394, Hiki-gun, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sakakibara", 
        "givenName": "Yasubumi", 
        "id": "sg:person.01273660767.57", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01273660767.57"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/76359.76371", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004063675"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/62212.62238", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014665507"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(92)90367-o", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025727180"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1968.1972", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038881641"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1022679002094", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038983587", 
          "https://doi.org/10.1023/a:1022679002094"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1044956201", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-03563-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044956201", 
          "https://doi.org/10.1007/978-3-662-03563-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-03563-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044956201", 
          "https://doi.org/10.1007/978-3-662-03563-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/48014.63140", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049677957"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1126/science.7725098", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062649072"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1126/science.7973651", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062650775"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1110620225", 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2001-04-25", 
    "datePublishedReg": "2001-04-25", 
    "description": "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 \u2260 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 efficiently learnable on DNA computer.", 
    "editor": [
      {
        "familyName": "Condon", 
        "givenName": "Anne", 
        "type": "Person"
      }, 
      {
        "familyName": "Rozenberg", 
        "givenName": "Grzegorz", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44992-2_15", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42076-7", 
        "978-3-540-44992-8"
      ], 
      "name": "DNA Computing", 
      "type": "Book"
    }, 
    "name": "Solving computational learning problems of Boolean formulae on DNA computers", 
    "pagination": "220-230", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44992-2_15"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "556e5705a930bdc0a08f8c05325be53e4250c6c0040ff3c0bc09e913ecab41fd"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017930394"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44992-2_15", 
      "https://app.dimensions.ai/details/publication/pub.1017930394"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:30", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000346_0000000346/records_99806_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-44992-2_15"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-44992-2_15'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-44992-2_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44992-2_15'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44992-2_15'


 

This table displays all metadata directly associated to this object as RDF triples.

103 TRIPLES      23 PREDICATES      37 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44992-2_15 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N509b1941009247a69e8bdcaea663622b
4 schema:citation sg:pub.10.1007/978-3-662-03563-4
5 sg:pub.10.1023/a:1022679002094
6 https://app.dimensions.ai/details/publication/pub.1044956201
7 https://app.dimensions.ai/details/publication/pub.1110620225
8 https://doi.org/10.1016/0304-3975(92)90367-o
9 https://doi.org/10.1126/science.7725098
10 https://doi.org/10.1126/science.7973651
11 https://doi.org/10.1145/1968.1972
12 https://doi.org/10.1145/48014.63140
13 https://doi.org/10.1145/62212.62238
14 https://doi.org/10.1145/76359.76371
15 schema:datePublished 2001-04-25
16 schema:datePublishedReg 2001-04-25
17 schema:description 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 ≠ 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 efficiently learnable on DNA computer.
18 schema:editor N6b4aab730aef4dd7955df9875e658222
19 schema:genre chapter
20 schema:inLanguage en
21 schema:isAccessibleForFree false
22 schema:isPartOf N84b7afee220b40e19bb88409dc49ef95
23 schema:name Solving computational learning problems of Boolean formulae on DNA computers
24 schema:pagination 220-230
25 schema:productId N1f37e5246d0149f49c676e37cf87e123
26 N87d2f8071f604887be57de305891f996
27 Na8e8e5c3bfef4c2097ee6581a5adbc2a
28 schema:publisher N4dbcf48b332d44d192c9c9548420ca16
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017930394
30 https://doi.org/10.1007/3-540-44992-2_15
31 schema:sdDatePublished 2019-04-16T05:30
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher Nb2e69de7b9414d0aa7ef1861f0220ac1
34 schema:url https://link.springer.com/10.1007%2F3-540-44992-2_15
35 sgo:license sg:explorer/license/
36 sgo:sdDataset chapters
37 rdf:type schema:Chapter
38 N1f37e5246d0149f49c676e37cf87e123 schema:name readcube_id
39 schema:value 556e5705a930bdc0a08f8c05325be53e4250c6c0040ff3c0bc09e913ecab41fd
40 rdf:type schema:PropertyValue
41 N2cd0760ce2964c26b5a8d7cb580ed9d2 schema:familyName Rozenberg
42 schema:givenName Grzegorz
43 rdf:type schema:Person
44 N4dbcf48b332d44d192c9c9548420ca16 schema:location Berlin, Heidelberg
45 schema:name Springer Berlin Heidelberg
46 rdf:type schema:Organisation
47 N509b1941009247a69e8bdcaea663622b rdf:first sg:person.01273660767.57
48 rdf:rest rdf:nil
49 N66c3f05f200943c4a821b53ae24e67d5 rdf:first N2cd0760ce2964c26b5a8d7cb580ed9d2
50 rdf:rest rdf:nil
51 N6b4aab730aef4dd7955df9875e658222 rdf:first Ncc709f0758764503aa8633d79d7a15e1
52 rdf:rest N66c3f05f200943c4a821b53ae24e67d5
53 N84b7afee220b40e19bb88409dc49ef95 schema:isbn 978-3-540-42076-7
54 978-3-540-44992-8
55 schema:name DNA Computing
56 rdf:type schema:Book
57 N87d2f8071f604887be57de305891f996 schema:name doi
58 schema:value 10.1007/3-540-44992-2_15
59 rdf:type schema:PropertyValue
60 Na8e8e5c3bfef4c2097ee6581a5adbc2a schema:name dimensions_id
61 schema:value pub.1017930394
62 rdf:type schema:PropertyValue
63 Nb2e69de7b9414d0aa7ef1861f0220ac1 schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 Ncc709f0758764503aa8633d79d7a15e1 schema:familyName Condon
66 schema:givenName Anne
67 rdf:type schema:Person
68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information and Computing Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
72 schema:name Artificial Intelligence and Image Processing
73 rdf:type schema:DefinedTerm
74 sg:person.01273660767.57 schema:affiliation https://www.grid.ac/institutes/grid.412773.4
75 schema:familyName Sakakibara
76 schema:givenName Yasubumi
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01273660767.57
78 rdf:type schema:Person
79 sg:pub.10.1007/978-3-662-03563-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044956201
80 https://doi.org/10.1007/978-3-662-03563-4
81 rdf:type schema:CreativeWork
82 sg:pub.10.1023/a:1022679002094 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038983587
83 https://doi.org/10.1023/a:1022679002094
84 rdf:type schema:CreativeWork
85 https://app.dimensions.ai/details/publication/pub.1044956201 schema:CreativeWork
86 https://app.dimensions.ai/details/publication/pub.1110620225 schema:CreativeWork
87 https://doi.org/10.1016/0304-3975(92)90367-o schema:sameAs https://app.dimensions.ai/details/publication/pub.1025727180
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1126/science.7725098 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062649072
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1126/science.7973651 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062650775
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1145/1968.1972 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038881641
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1145/48014.63140 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049677957
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1145/62212.62238 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014665507
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1145/76359.76371 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004063675
100 rdf:type schema:CreativeWork
101 https://www.grid.ac/institutes/grid.412773.4 schema:alternateName Tokyo Denki University
102 schema:name Department of Information Sciences, Tokyo Denki University, 350-0394, Hiki-gun, Saitama, Japan
103 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...