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/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"
          }, 
          {
            "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"
          }
        ], 
        "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": "2022-01-01T18:45", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_732.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 N2565319784304a1ea34a968b247c263a
    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 N04882b58ce3944569cbeed82a7917910
    14 Na6b4a4b2fd8b4ea99f09cfa1063669d2
    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 N2847e47f1d99440cbbba147f0e92532d
    43 Na47d8e9e2b8a4ad78910375f074b2489
    44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090880786
    45 https://doi.org/10.1007/s00453-017-0331-3
    46 schema:sdDatePublished 2022-01-01T18:45
    47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    48 schema:sdPublisher Nb09721392e204fdf9f83c6ed0b7a837b
    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 N04882b58ce3944569cbeed82a7917910 schema:issueNumber 7
    54 rdf:type schema:PublicationIssue
    55 N2565319784304a1ea34a968b247c263a rdf:first sg:person.015611460437.34
    56 rdf:rest Nad8f8d83fdd644b9be6f1d7fca670c21
    57 N2847e47f1d99440cbbba147f0e92532d schema:name dimensions_id
    58 schema:value pub.1090880786
    59 rdf:type schema:PropertyValue
    60 Na47d8e9e2b8a4ad78910375f074b2489 schema:name doi
    61 schema:value 10.1007/s00453-017-0331-3
    62 rdf:type schema:PropertyValue
    63 Na6b4a4b2fd8b4ea99f09cfa1063669d2 schema:volumeNumber 80
    64 rdf:type schema:PublicationVolume
    65 Nad8f8d83fdd644b9be6f1d7fca670c21 rdf:first sg:person.016240662443.33
    66 rdf:rest Ne7dec0b44dfb4326ab39a6bfd2c7ce37
    67 Nb09721392e204fdf9f83c6ed0b7a837b schema:name Springer Nature - SN SciGraph project
    68 rdf:type schema:Organization
    69 Ne7dec0b44dfb4326ab39a6bfd2c7ce37 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)


    ...