Dynamic Complexity of the Dyck Reachability View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2017

AUTHORS

Patricia Bouyer , Vincent Jugé

ABSTRACT

Dynamic complexity is concerned with updating the output of a problem when the input is slightly changed. We study the dynamic complexity of Dyck reachability problems in directed and undirected graphs, where updates may add or delete edges. We show a strong dichotomy between such problems, based on the size of the Dyck alphabet. Some of them are \(\mathsf {P}\)-complete (under a strong notion of reduction) while the others lie either in \(\mathsf {DynFO}\) or in \(\mathsf {NL}\). More... »

PAGES

265-280

References to SciGraph publications

  • 2009. Reachability in Succinct and Parametric One-Counter Automata in CONCUR 2009 - CONCURRENCY THEORY
  • 1999. Descriptive Complexity in NONE
  • 2007-06. Dynamic Complexity Theory Revisited in THEORY OF COMPUTING SYSTEMS
  • 2015. Reachability is in DynFO in AUTOMATA, LANGUAGES, AND PROGRAMMING
  • Book

    TITLE

    Foundations of Software Science and Computation Structures

    ISBN

    978-3-662-54457-0
    978-3-662-54458-7

    From Grant

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-662-54458-7_16

    DOI

    http://dx.doi.org/10.1007/978-3-662-54458-7_16

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "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": "Laboratoire Sp\u00e9cification et V\u00e9rification", 
              "id": "https://www.grid.ac/institutes/grid.464035.0", 
              "name": [
                "LSV, CNRS & ENS Cachan, Univ. Paris-Saclay Cachan France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bouyer", 
            "givenName": "Patricia", 
            "id": "sg:person.014467443251.73", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014467443251.73"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Laboratoire Sp\u00e9cification et V\u00e9rification", 
              "id": "https://www.grid.ac/institutes/grid.464035.0", 
              "name": [
                "LSV, CNRS & ENS Cachan, Univ. Paris-Saclay Cachan France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Jug\u00e9", 
            "givenName": "Vincent", 
            "id": "sg:person.010665014447.72", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010665014447.72"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1006/jcss.1997.1520", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005860726"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-0000(90)90022-d", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007070716"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-006-1312-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007472069", 
              "https://doi.org/10.1007/s00224-006-1312-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(02)00740-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018943846"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-0539-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019353558", 
              "https://doi.org/10.1007/978-1-4612-0539-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-0539-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019353558", 
              "https://doi.org/10.1007/978-1-4612-0539-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-04081-8_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023352610", 
              "https://doi.org/10.1007/978-3-642-04081-8_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/inco.1995.1102", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027609614"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-47666-6_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028882142", 
              "https://doi.org/10.1007/978-3-662-47666-6_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(94)90159-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037918384"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2287718.2287719", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046779343"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/logcom/exp037", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059876288"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/logcom/exp037", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059876288"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/lics.2002.1029839", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095359183"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2017", 
        "datePublishedReg": "2017-01-01", 
        "description": "Dynamic complexity is concerned with updating the output of a problem when the input is slightly changed. We study the dynamic complexity of Dyck reachability problems in directed and undirected graphs, where updates may add or delete edges. We show a strong dichotomy between such problems, based on the size of the Dyck alphabet. Some of them are \\(\\mathsf {P}\\)-complete (under a strong notion of reduction) while the others lie either in \\(\\mathsf {DynFO}\\) or in \\(\\mathsf {NL}\\).", 
        "editor": [
          {
            "familyName": "Esparza", 
            "givenName": "Javier", 
            "type": "Person"
          }, 
          {
            "familyName": "Murawski", 
            "givenName": "Andrzej S.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-662-54458-7_16", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3795792", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": {
          "isbn": [
            "978-3-662-54457-0", 
            "978-3-662-54458-7"
          ], 
          "name": "Foundations of Software Science and Computation Structures", 
          "type": "Book"
        }, 
        "name": "Dynamic Complexity of the Dyck Reachability", 
        "pagination": "265-280", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-662-54458-7_16"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "c919fdb4c89ab5a65ff01193557bebe00821670a23a3c7b3ff865cfa7b31fe93"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1084723409"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-662-54458-7_16", 
          "https://app.dimensions.ai/details/publication/pub.1084723409"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T11:44", 
        "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/0000000001_0000000264/records_8660_00000331.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-662-54458-7_16"
      }
    ]
     

    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/978-3-662-54458-7_16'

    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/978-3-662-54458-7_16'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-54458-7_16'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-54458-7_16'


     

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

    119 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-662-54458-7_16 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N9ebc3616bc06433e95479b33d271ee64
    4 schema:citation sg:pub.10.1007/978-1-4612-0539-5
    5 sg:pub.10.1007/978-3-642-04081-8_25
    6 sg:pub.10.1007/978-3-662-47666-6_13
    7 sg:pub.10.1007/s00224-006-1312-0
    8 https://doi.org/10.1006/inco.1995.1102
    9 https://doi.org/10.1006/jcss.1997.1520
    10 https://doi.org/10.1016/0022-0000(90)90022-d
    11 https://doi.org/10.1016/0304-3975(94)90159-7
    12 https://doi.org/10.1016/s0304-3975(02)00740-5
    13 https://doi.org/10.1093/logcom/exp037
    14 https://doi.org/10.1109/lics.2002.1029839
    15 https://doi.org/10.1145/2287718.2287719
    16 schema:datePublished 2017
    17 schema:datePublishedReg 2017-01-01
    18 schema:description Dynamic complexity is concerned with updating the output of a problem when the input is slightly changed. We study the dynamic complexity of Dyck reachability problems in directed and undirected graphs, where updates may add or delete edges. We show a strong dichotomy between such problems, based on the size of the Dyck alphabet. Some of them are \(\mathsf {P}\)-complete (under a strong notion of reduction) while the others lie either in \(\mathsf {DynFO}\) or in \(\mathsf {NL}\).
    19 schema:editor N48f1c8927ac7419585fb66f342193253
    20 schema:genre chapter
    21 schema:inLanguage en
    22 schema:isAccessibleForFree true
    23 schema:isPartOf N4ad62453c9b64b03a8e5dbbcbcf96f5c
    24 schema:name Dynamic Complexity of the Dyck Reachability
    25 schema:pagination 265-280
    26 schema:productId N459c92efcd214a2b9d1f9fd42287a1e2
    27 N7c4cae8d64114d209ea5513488bad4f0
    28 Nff36dd07a7fd4eeda45a6b321dfd5d26
    29 schema:publisher N34b410a3ff0041588d5b0738f34ae3ca
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084723409
    31 https://doi.org/10.1007/978-3-662-54458-7_16
    32 schema:sdDatePublished 2019-04-15T11:44
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher Nb8be2aa7ec2e4a2cacdc05658df5fd17
    35 schema:url http://link.springer.com/10.1007/978-3-662-54458-7_16
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset chapters
    38 rdf:type schema:Chapter
    39 N06f20728dfc44d27982301389093d43e rdf:first N1c8bddd5ada149e7980780d03274dc27
    40 rdf:rest rdf:nil
    41 N1c8bddd5ada149e7980780d03274dc27 schema:familyName Murawski
    42 schema:givenName Andrzej S.
    43 rdf:type schema:Person
    44 N32fca48242704c03845c92e98c04b84d schema:familyName Esparza
    45 schema:givenName Javier
    46 rdf:type schema:Person
    47 N34b410a3ff0041588d5b0738f34ae3ca schema:location Berlin, Heidelberg
    48 schema:name Springer Berlin Heidelberg
    49 rdf:type schema:Organisation
    50 N459c92efcd214a2b9d1f9fd42287a1e2 schema:name doi
    51 schema:value 10.1007/978-3-662-54458-7_16
    52 rdf:type schema:PropertyValue
    53 N48f1c8927ac7419585fb66f342193253 rdf:first N32fca48242704c03845c92e98c04b84d
    54 rdf:rest N06f20728dfc44d27982301389093d43e
    55 N4ad62453c9b64b03a8e5dbbcbcf96f5c schema:isbn 978-3-662-54457-0
    56 978-3-662-54458-7
    57 schema:name Foundations of Software Science and Computation Structures
    58 rdf:type schema:Book
    59 N7c4cae8d64114d209ea5513488bad4f0 schema:name dimensions_id
    60 schema:value pub.1084723409
    61 rdf:type schema:PropertyValue
    62 N9ebc3616bc06433e95479b33d271ee64 rdf:first sg:person.014467443251.73
    63 rdf:rest Nbf722df835c6421f92352b13fe92f37c
    64 Nb8be2aa7ec2e4a2cacdc05658df5fd17 schema:name Springer Nature - SN SciGraph project
    65 rdf:type schema:Organization
    66 Nbf722df835c6421f92352b13fe92f37c rdf:first sg:person.010665014447.72
    67 rdf:rest rdf:nil
    68 Nff36dd07a7fd4eeda45a6b321dfd5d26 schema:name readcube_id
    69 schema:value c919fdb4c89ab5a65ff01193557bebe00821670a23a3c7b3ff865cfa7b31fe93
    70 rdf:type schema:PropertyValue
    71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Information and Computing Sciences
    73 rdf:type schema:DefinedTerm
    74 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Computation Theory and Mathematics
    76 rdf:type schema:DefinedTerm
    77 sg:grant.3795792 http://pending.schema.org/fundedItem sg:pub.10.1007/978-3-662-54458-7_16
    78 rdf:type schema:MonetaryGrant
    79 sg:person.010665014447.72 schema:affiliation https://www.grid.ac/institutes/grid.464035.0
    80 schema:familyName Jugé
    81 schema:givenName Vincent
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010665014447.72
    83 rdf:type schema:Person
    84 sg:person.014467443251.73 schema:affiliation https://www.grid.ac/institutes/grid.464035.0
    85 schema:familyName Bouyer
    86 schema:givenName Patricia
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014467443251.73
    88 rdf:type schema:Person
    89 sg:pub.10.1007/978-1-4612-0539-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019353558
    90 https://doi.org/10.1007/978-1-4612-0539-5
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/978-3-642-04081-8_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023352610
    93 https://doi.org/10.1007/978-3-642-04081-8_25
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/978-3-662-47666-6_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028882142
    96 https://doi.org/10.1007/978-3-662-47666-6_13
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/s00224-006-1312-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007472069
    99 https://doi.org/10.1007/s00224-006-1312-0
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1006/inco.1995.1102 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027609614
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1006/jcss.1997.1520 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005860726
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/0022-0000(90)90022-d schema:sameAs https://app.dimensions.ai/details/publication/pub.1007070716
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/0304-3975(94)90159-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037918384
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1016/s0304-3975(02)00740-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018943846
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1093/logcom/exp037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059876288
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1109/lics.2002.1029839 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095359183
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1145/2287718.2287719 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046779343
    116 rdf:type schema:CreativeWork
    117 https://www.grid.ac/institutes/grid.464035.0 schema:alternateName Laboratoire Spécification et Vérification
    118 schema:name LSV, CNRS & ENS Cachan, Univ. Paris-Saclay Cachan France
    119 rdf:type schema:Organization
     




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


    ...