Verification in staged tile self-assembly View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2019-03

AUTHORS

Robert Schweller, Andrew Winslow, Tim Wylie

ABSTRACT

We prove the unique assembly and unique shape verification problems, benchmark measures of self-assembly model power, are coNPNP-hard and contained in PSPACE (and in Π2sP for staged systems with s stages). En route, we prove that unique shape verification problem in the 2HAM is coNPNP-complete.

PAGES

107-117

References to SciGraph publications

  • 2015-06. Staged self-assembly and polyomino context-free grammars in NATURAL COMPUTING
  • 2014. Producibility in Hierarchical Self-assembly in UNCONVENTIONAL COMPUTATION AND NATURAL COMPUTATION
  • 2008-09. Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues in NATURAL COMPUTING
  • 2011. One-Dimensional Staged Self-assembly in DNA COMPUTING AND MOLECULAR PROGRAMMING
  • 2015. New Geometric Algorithms for Fully Connected Staged Self-Assembly in DNA COMPUTING AND MOLECULAR PROGRAMMING
  • 2018-04. Optimal Staged Self-Assembly of General Shapes in ALGORITHMICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11047-018-9701-2

    DOI

    http://dx.doi.org/10.1007/s11047-018-9701-2

    DIMENSIONS

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


    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", 
        "author": [
          {
            "affiliation": {
              "alternateName": "The University of Texas Rio Grande Valley", 
              "id": "https://www.grid.ac/institutes/grid.449717.8", 
              "name": [
                "Department of Computer Science, University of Texas Rio Grande Valley, Edinburg, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Schweller", 
            "givenName": "Robert", 
            "id": "sg:person.014737303547.10", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014737303547.10"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "The University of Texas Rio Grande Valley", 
              "id": "https://www.grid.ac/institutes/grid.449717.8", 
              "name": [
                "Department of Computer Science, University of Texas Rio Grande Valley, Edinburg, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Winslow", 
            "givenName": "Andrew", 
            "id": "sg:person.015400117412.15", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015400117412.15"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "The University of Texas Rio Grande Valley", 
              "id": "https://www.grid.ac/institutes/grid.449717.8", 
              "name": [
                "Department of Computer Science, University of Texas Rio Grande Valley, Edinburg, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wylie", 
            "givenName": "Tim", 
            "id": "sg:person.010132573477.74", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010132573477.74"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-319-21999-8_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002914821", 
              "https://doi.org/10.1007/978-3-319-21999-8_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11047-014-9423-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014276702", 
              "https://doi.org/10.1007/s11047-014-9423-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11047-008-9073-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028186068", 
              "https://doi.org/10.1007/s11047-008-9073-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/582475.582484", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028441037"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-23638-9_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034369103", 
              "https://doi.org/10.1007/978-3-642-23638-9_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-23638-9_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034369103", 
              "https://doi.org/10.1007/978-3-642-23638-9_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-08123-6_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042101347", 
              "https://doi.org/10.1007/978-3-319-08123-6_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(76)90061-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048647089"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/509907.509913", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050576543"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539704446037", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879561"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-017-0318-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1085140394", 
              "https://doi.org/10.1007/s00453-017-0318-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-017-0318-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1085140394", 
              "https://doi.org/10.1007/s00453-017-0318-0"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-03", 
        "datePublishedReg": "2019-03-01", 
        "description": "We prove the unique assembly and unique shape verification problems, benchmark measures of self-assembly model power, are coNPNP-hard and contained in PSPACE (and in \u03a02sP for staged systems with s stages). En route, we prove that unique shape verification problem in the 2HAM is coNPNP-complete.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s11047-018-9701-2", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3000850", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.4314453", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1033918", 
            "issn": [
              "1567-7818", 
              "1572-9796"
            ], 
            "name": "Natural Computing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "18"
          }
        ], 
        "name": "Verification in staged tile self-assembly", 
        "pagination": "107-117", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "1e28416adba4ef4d3d0403deaef438ef0d56ba477998d5eba7a72ff101fc8569"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11047-018-9701-2"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1105944578"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11047-018-9701-2", 
          "https://app.dimensions.ai/details/publication/pub.1105944578"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T09:11", 
        "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/0000000338_0000000338/records_47976_00000002.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs11047-018-9701-2"
      }
    ]
     

    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/s11047-018-9701-2'

    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/s11047-018-9701-2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11047-018-9701-2'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11047-018-9701-2'


     

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

    107 TRIPLES      20 PREDICATES      35 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11047-018-9701-2 schema:author N8caaf46567a1401f992d06dda6b42c97
    2 schema:citation sg:pub.10.1007/978-3-319-08123-6_12
    3 sg:pub.10.1007/978-3-319-21999-8_7
    4 sg:pub.10.1007/978-3-642-23638-9_10
    5 sg:pub.10.1007/s00453-017-0318-0
    6 sg:pub.10.1007/s11047-008-9073-0
    7 sg:pub.10.1007/s11047-014-9423-z
    8 https://doi.org/10.1016/0304-3975(76)90061-x
    9 https://doi.org/10.1137/s0097539704446037
    10 https://doi.org/10.1145/509907.509913
    11 https://doi.org/10.1145/582475.582484
    12 schema:datePublished 2019-03
    13 schema:datePublishedReg 2019-03-01
    14 schema:description We prove the unique assembly and unique shape verification problems, benchmark measures of self-assembly model power, are coNPNP-hard and contained in PSPACE (and in Π2sP for staged systems with s stages). En route, we prove that unique shape verification problem in the 2HAM is coNPNP-complete.
    15 schema:genre research_article
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N4511eb8170894499ac81034aa5d460a3
    19 Nf493832ab1034bdfb2dfffaa3750011a
    20 sg:journal.1033918
    21 schema:name Verification in staged tile self-assembly
    22 schema:pagination 107-117
    23 schema:productId N5a0ef79835064661ac218b4e238bce37
    24 Ne9a759d3071345beaaf9efe88d7f73e8
    25 Nf1cfa9ec68da40c0b5d15e87261b57fe
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105944578
    27 https://doi.org/10.1007/s11047-018-9701-2
    28 schema:sdDatePublished 2019-04-11T09:11
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher N2a82e245ed824b8da81150fa92c90d30
    31 schema:url https://link.springer.com/10.1007%2Fs11047-018-9701-2
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset articles
    34 rdf:type schema:ScholarlyArticle
    35 N2a82e245ed824b8da81150fa92c90d30 schema:name Springer Nature - SN SciGraph project
    36 rdf:type schema:Organization
    37 N3906e542a40d4682a527a53547b67409 rdf:first sg:person.015400117412.15
    38 rdf:rest Ned2cccf537da48a2895d2ef8461690af
    39 N4511eb8170894499ac81034aa5d460a3 schema:issueNumber 1
    40 rdf:type schema:PublicationIssue
    41 N5a0ef79835064661ac218b4e238bce37 schema:name readcube_id
    42 schema:value 1e28416adba4ef4d3d0403deaef438ef0d56ba477998d5eba7a72ff101fc8569
    43 rdf:type schema:PropertyValue
    44 N8caaf46567a1401f992d06dda6b42c97 rdf:first sg:person.014737303547.10
    45 rdf:rest N3906e542a40d4682a527a53547b67409
    46 Ne9a759d3071345beaaf9efe88d7f73e8 schema:name doi
    47 schema:value 10.1007/s11047-018-9701-2
    48 rdf:type schema:PropertyValue
    49 Ned2cccf537da48a2895d2ef8461690af rdf:first sg:person.010132573477.74
    50 rdf:rest rdf:nil
    51 Nf1cfa9ec68da40c0b5d15e87261b57fe schema:name dimensions_id
    52 schema:value pub.1105944578
    53 rdf:type schema:PropertyValue
    54 Nf493832ab1034bdfb2dfffaa3750011a schema:volumeNumber 18
    55 rdf:type schema:PublicationVolume
    56 sg:grant.3000850 http://pending.schema.org/fundedItem sg:pub.10.1007/s11047-018-9701-2
    57 rdf:type schema:MonetaryGrant
    58 sg:grant.4314453 http://pending.schema.org/fundedItem sg:pub.10.1007/s11047-018-9701-2
    59 rdf:type schema:MonetaryGrant
    60 sg:journal.1033918 schema:issn 1567-7818
    61 1572-9796
    62 schema:name Natural Computing
    63 rdf:type schema:Periodical
    64 sg:person.010132573477.74 schema:affiliation https://www.grid.ac/institutes/grid.449717.8
    65 schema:familyName Wylie
    66 schema:givenName Tim
    67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010132573477.74
    68 rdf:type schema:Person
    69 sg:person.014737303547.10 schema:affiliation https://www.grid.ac/institutes/grid.449717.8
    70 schema:familyName Schweller
    71 schema:givenName Robert
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014737303547.10
    73 rdf:type schema:Person
    74 sg:person.015400117412.15 schema:affiliation https://www.grid.ac/institutes/grid.449717.8
    75 schema:familyName Winslow
    76 schema:givenName Andrew
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015400117412.15
    78 rdf:type schema:Person
    79 sg:pub.10.1007/978-3-319-08123-6_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042101347
    80 https://doi.org/10.1007/978-3-319-08123-6_12
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/978-3-319-21999-8_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002914821
    83 https://doi.org/10.1007/978-3-319-21999-8_7
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/978-3-642-23638-9_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034369103
    86 https://doi.org/10.1007/978-3-642-23638-9_10
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/s00453-017-0318-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085140394
    89 https://doi.org/10.1007/s00453-017-0318-0
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/s11047-008-9073-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028186068
    92 https://doi.org/10.1007/s11047-008-9073-0
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/s11047-014-9423-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1014276702
    95 https://doi.org/10.1007/s11047-014-9423-z
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/0304-3975(76)90061-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1048647089
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1137/s0097539704446037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879561
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1145/509907.509913 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050576543
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1145/582475.582484 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028441037
    104 rdf:type schema:CreativeWork
    105 https://www.grid.ac/institutes/grid.449717.8 schema:alternateName The University of Texas Rio Grande Valley
    106 schema:name Department of Computer Science, University of Texas Rio Grande Valley, Edinburg, USA
    107 rdf:type schema:Organization
     




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


    ...