Constant-Time Tree Traversal and Subtree Equality Check for Grammar-Compressed Trees View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2017-07-24

AUTHORS

Markus Lohrey, Sebastian Maneth, Carl Philipp Reh

ABSTRACT

A linear space data structure for grammar-compressed trees is presented which allows to carry out tree traversal operations and subtree equality checks in constant time. A traversal step consists of moving to the parent or to the ith child of a node.

PAGES

2082-2105

References to SciGraph publications

  • 2000. The LCA Problem Revisited in LATIN 2000: THEORETICAL INFORMATICS
  • 2014-05-25. XML Compression via Directed Acyclic Graphs in THEORY OF COMPUTING SYSTEMS
  • 2015-06-20. Tree Compression with Top Trees Revisited in EXPERIMENTAL ALGORITHMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-017-0331-3

    DOI

    http://dx.doi.org/10.1007/s00453-017-0331-3

    DIMENSIONS

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


    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/06", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Biological Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0607", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Plant Biology", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Universit\u00e4t Siegen, Siegen, Germany", 
              "id": "http://www.grid.ac/institutes/grid.5836.8", 
              "name": [
                "Universit\u00e4t Siegen, Siegen, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lohrey", 
            "givenName": "Markus", 
            "id": "sg:person.015611460437.34", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015611460437.34"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics and Informatics, Universit\u00e4t Bremen, Bremen, Germany", 
              "id": "http://www.grid.ac/institutes/grid.7704.4", 
              "name": [
                "Department of Mathematics and Informatics, Universit\u00e4t Bremen, Bremen, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Maneth", 
            "givenName": "Sebastian", 
            "id": "sg:person.016240662443.33", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Universit\u00e4t Siegen, Siegen, Germany", 
              "id": "http://www.grid.ac/institutes/grid.5836.8", 
              "name": [
                "Universit\u00e4t Siegen, Siegen, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Reh", 
            "givenName": "Carl Philipp", 
            "id": "sg:person.010543570163.13", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010543570163.13"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-319-20086-6_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008794190", 
              "https://doi.org/10.1007/978-3-319-20086-6_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-014-9544-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043536406", 
              "https://doi.org/10.1007/s00224-014-9544-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/10719839_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037071768", 
              "https://doi.org/10.1007/10719839_9"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2017-07-24", 
        "datePublishedReg": "2017-07-24", 
        "description": "A linear space data structure for grammar-compressed trees is presented which allows to carry out tree traversal operations and subtree equality checks in constant time. A traversal step consists of moving to the parent or to the ith child of a node.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00453-017-0331-3", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "7", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "80"
          }
        ], 
        "keywords": [
          "trees", 
          "operation", 
          "structure", 
          "step", 
          "time", 
          "check", 
          "constant time", 
          "parents", 
          "data structure", 
          "nodes", 
          "traversal", 
          "traversal operations", 
          "tree traversal", 
          "space data structure", 
          "children", 
          "linear space data structure", 
          "grammar-compressed trees", 
          "tree traversal operations", 
          "equality checks", 
          "traversal steps", 
          "ith child", 
          "Time Tree Traversal", 
          "Subtree Equality Check", 
          "Grammar-Compressed Trees"
        ], 
        "name": "Constant-Time Tree Traversal and Subtree Equality Check for Grammar-Compressed Trees", 
        "pagination": "2082-2105", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1090880786"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-017-0331-3"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-017-0331-3", 
          "https://app.dimensions.ai/details/publication/pub.1090880786"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:38", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_721.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00453-017-0331-3"
      }
    ]
     

    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/s00453-017-0331-3'

    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/s00453-017-0331-3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-017-0331-3'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-017-0331-3'


     

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

    111 TRIPLES      22 PREDICATES      52 URIs      41 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-017-0331-3 schema:about anzsrc-for:06
    2 anzsrc-for:0607
    3 schema:author N3b18b3a086f94332921ff56ca4977611
    4 schema:citation sg:pub.10.1007/10719839_9
    5 sg:pub.10.1007/978-3-319-20086-6_2
    6 sg:pub.10.1007/s00224-014-9544-x
    7 schema:datePublished 2017-07-24
    8 schema:datePublishedReg 2017-07-24
    9 schema:description A linear space data structure for grammar-compressed trees is presented which allows to carry out tree traversal operations and subtree equality checks in constant time. A traversal step consists of moving to the parent or to the ith child of a node.
    10 schema:genre article
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N257efd2b0cd7412599450fd6b35d29ef
    14 N54d2e60b18aa4637a4dde2deec050f16
    15 sg:journal.1047644
    16 schema:keywords Grammar-Compressed Trees
    17 Subtree Equality Check
    18 Time Tree Traversal
    19 check
    20 children
    21 constant time
    22 data structure
    23 equality checks
    24 grammar-compressed trees
    25 ith child
    26 linear space data structure
    27 nodes
    28 operation
    29 parents
    30 space data structure
    31 step
    32 structure
    33 time
    34 traversal
    35 traversal operations
    36 traversal steps
    37 tree traversal
    38 tree traversal operations
    39 trees
    40 schema:name Constant-Time Tree Traversal and Subtree Equality Check for Grammar-Compressed Trees
    41 schema:pagination 2082-2105
    42 schema:productId N763b82b3f59d49e480170501005aff62
    43 Nad7fc5e43cd5451aa7122ba8add60767
    44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090880786
    45 https://doi.org/10.1007/s00453-017-0331-3
    46 schema:sdDatePublished 2021-12-01T19:38
    47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    48 schema:sdPublisher Ndb26b500cc1a49758e5507c4bf98b5ad
    49 schema:url https://doi.org/10.1007/s00453-017-0331-3
    50 sgo:license sg:explorer/license/
    51 sgo:sdDataset articles
    52 rdf:type schema:ScholarlyArticle
    53 N051a44f19245463abb5934d9ca585659 rdf:first sg:person.016240662443.33
    54 rdf:rest Ndce9403247234564b393b46afea493bc
    55 N257efd2b0cd7412599450fd6b35d29ef schema:issueNumber 7
    56 rdf:type schema:PublicationIssue
    57 N3b18b3a086f94332921ff56ca4977611 rdf:first sg:person.015611460437.34
    58 rdf:rest N051a44f19245463abb5934d9ca585659
    59 N54d2e60b18aa4637a4dde2deec050f16 schema:volumeNumber 80
    60 rdf:type schema:PublicationVolume
    61 N763b82b3f59d49e480170501005aff62 schema:name doi
    62 schema:value 10.1007/s00453-017-0331-3
    63 rdf:type schema:PropertyValue
    64 Nad7fc5e43cd5451aa7122ba8add60767 schema:name dimensions_id
    65 schema:value pub.1090880786
    66 rdf:type schema:PropertyValue
    67 Ndb26b500cc1a49758e5507c4bf98b5ad schema:name Springer Nature - SN SciGraph project
    68 rdf:type schema:Organization
    69 Ndce9403247234564b393b46afea493bc rdf:first sg:person.010543570163.13
    70 rdf:rest rdf:nil
    71 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Biological Sciences
    73 rdf:type schema:DefinedTerm
    74 anzsrc-for:0607 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Plant Biology
    76 rdf:type schema:DefinedTerm
    77 sg:journal.1047644 schema:issn 0178-4617
    78 1432-0541
    79 schema:name Algorithmica
    80 schema:publisher Springer Nature
    81 rdf:type schema:Periodical
    82 sg:person.010543570163.13 schema:affiliation grid-institutes:grid.5836.8
    83 schema:familyName Reh
    84 schema:givenName Carl Philipp
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010543570163.13
    86 rdf:type schema:Person
    87 sg:person.015611460437.34 schema:affiliation grid-institutes:grid.5836.8
    88 schema:familyName Lohrey
    89 schema:givenName Markus
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015611460437.34
    91 rdf:type schema:Person
    92 sg:person.016240662443.33 schema:affiliation grid-institutes:grid.7704.4
    93 schema:familyName Maneth
    94 schema:givenName Sebastian
    95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
    96 rdf:type schema:Person
    97 sg:pub.10.1007/10719839_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037071768
    98 https://doi.org/10.1007/10719839_9
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/978-3-319-20086-6_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008794190
    101 https://doi.org/10.1007/978-3-319-20086-6_2
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/s00224-014-9544-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043536406
    104 https://doi.org/10.1007/s00224-014-9544-x
    105 rdf:type schema:CreativeWork
    106 grid-institutes:grid.5836.8 schema:alternateName Universität Siegen, Siegen, Germany
    107 schema:name Universität Siegen, Siegen, Germany
    108 rdf:type schema:Organization
    109 grid-institutes:grid.7704.4 schema:alternateName Department of Mathematics and Informatics, Universität Bremen, Bremen, Germany
    110 schema:name Department of Mathematics and Informatics, Universität Bremen, Bremen, Germany
    111 rdf:type schema:Organization
     




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


    ...