Grammar-Based Compression of Unranked Trees View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2018-04-25

AUTHORS

Adrià Gascón , Markus Lohrey , Sebastian Maneth , Carl Philipp Reh , Kurt Sieber

ABSTRACT

We introduce forest straight-line programs (FSLPs) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and generalize tree straight-line programs. We compare the succinctness of FSLPs with two other compression schemes for unranked trees: top dags and tree straight-line programs of first-child/next sibling encodings. Efficient translations between these formalisms are provided. Finally, we show that equality of unranked trees in the setting where certain symbols are associative or commutative can be tested in polynomial time. This generalizes previous results for testing isomorphism of compressed unordered ranked trees. More... »

PAGES

118-131

Book

TITLE

Computer Science – Theory and Applications

ISBN

978-3-319-90529-7
978-3-319-90530-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-90530-3_11

DOI

http://dx.doi.org/10.1007/978-3-319-90530-3_11

DIMENSIONS

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


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/07", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Agricultural and Veterinary Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0705", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Forestry Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Warwick University and Alan Turing Institute, Warwick, UK", 
          "id": "http://www.grid.ac/institutes/grid.7372.1", 
          "name": [
            "Warwick University and Alan Turing Institute, Warwick, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gasc\u00f3n", 
        "givenName": "Adri\u00e0", 
        "id": "sg:person.010152520633.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010152520633.58"
        ], 
        "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": "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": "Universit\u00e4t Bremen, Bremen, Germany", 
          "id": "http://www.grid.ac/institutes/grid.7704.4", 
          "name": [
            "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"
      }, 
      {
        "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": "Sieber", 
        "givenName": "Kurt", 
        "id": "sg:person.016214735032.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016214735032.21"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2018-04-25", 
    "datePublishedReg": "2018-04-25", 
    "description": "We introduce forest straight-line programs (FSLPs) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and generalize tree straight-line programs. We compare the succinctness of FSLPs with two other compression schemes for unranked trees: top dags and tree straight-line programs of first-child/next sibling encodings. Efficient translations between these formalisms are provided. Finally, we show that equality of unranked trees in the setting where certain symbols are associative or commutative can be tested in polynomial time. This generalizes previous results for testing isomorphism of compressed unordered ranked trees.", 
    "editor": [
      {
        "familyName": "Fomin", 
        "givenName": "Fedor V.", 
        "type": "Person"
      }, 
      {
        "familyName": "Podolskii", 
        "givenName": "Vladimir V.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-90530-3_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-90529-7", 
        "978-3-319-90530-3"
      ], 
      "name": "Computer Science \u2013 Theory and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "efficient translation", 
      "trees", 
      "translation", 
      "DAG", 
      "previous results", 
      "program", 
      "results", 
      "time", 
      "straight-line programs", 
      "encoding", 
      "compression scheme", 
      "unranked trees", 
      "setting", 
      "polynomial time", 
      "representation", 
      "node-labeled tree", 
      "operation", 
      "succinctness", 
      "scheme", 
      "certain symbols", 
      "symbols", 
      "grammar", 
      "compression", 
      "algebra", 
      "formalism", 
      "isomorphism", 
      "equality", 
      "FSLPs", 
      "forest algebras", 
      "tree straight-line programs", 
      "succinctness of FSLPs", 
      "top dags"
    ], 
    "name": "Grammar-Based Compression of Unranked Trees", 
    "pagination": "118-131", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1103771347"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-90530-3_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-90530-3_11", 
      "https://app.dimensions.ai/details/publication/pub.1103771347"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:53", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_267.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-90530-3_11"
  }
]
 

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-319-90530-3_11'

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-319-90530-3_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-90530-3_11'

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-319-90530-3_11'


 

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

131 TRIPLES      23 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-90530-3_11 schema:about anzsrc-for:07
2 anzsrc-for:0705
3 schema:author N4cd3f783d9b342019b19732521fc61b7
4 schema:datePublished 2018-04-25
5 schema:datePublishedReg 2018-04-25
6 schema:description We introduce forest straight-line programs (FSLPs) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and generalize tree straight-line programs. We compare the succinctness of FSLPs with two other compression schemes for unranked trees: top dags and tree straight-line programs of first-child/next sibling encodings. Efficient translations between these formalisms are provided. Finally, we show that equality of unranked trees in the setting where certain symbols are associative or commutative can be tested in polynomial time. This generalizes previous results for testing isomorphism of compressed unordered ranked trees.
7 schema:editor N604aa033567541a6a904a089304ddb6a
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nddfdaabd442f43ec9eb03b0f89ce50bd
12 schema:keywords DAG
13 FSLPs
14 algebra
15 certain symbols
16 compression
17 compression scheme
18 efficient translation
19 encoding
20 equality
21 forest algebras
22 formalism
23 grammar
24 isomorphism
25 node-labeled tree
26 operation
27 polynomial time
28 previous results
29 program
30 representation
31 results
32 scheme
33 setting
34 straight-line programs
35 succinctness
36 succinctness of FSLPs
37 symbols
38 time
39 top dags
40 translation
41 tree straight-line programs
42 trees
43 unranked trees
44 schema:name Grammar-Based Compression of Unranked Trees
45 schema:pagination 118-131
46 schema:productId N4bccc4b95ceb454280e524334b10bbe0
47 Nd45e3de98b9140f7818e18efea867ac7
48 schema:publisher N45f98d394a06487480535a01f8e98e84
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103771347
50 https://doi.org/10.1007/978-3-319-90530-3_11
51 schema:sdDatePublished 2021-11-01T18:53
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N6c83f6dc3fa74934a35583abbe032f98
54 schema:url https://doi.org/10.1007/978-3-319-90530-3_11
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N19977948934d4d3b9d422e5211fa9a1d rdf:first sg:person.016240662443.33
59 rdf:rest N543754c3c3054e1fa8799c43c5a9a2e3
60 N257c6db51e7a4dbeb33f638bb46184a3 schema:familyName Fomin
61 schema:givenName Fedor V.
62 rdf:type schema:Person
63 N45f98d394a06487480535a01f8e98e84 schema:name Springer Nature
64 rdf:type schema:Organisation
65 N4bccc4b95ceb454280e524334b10bbe0 schema:name doi
66 schema:value 10.1007/978-3-319-90530-3_11
67 rdf:type schema:PropertyValue
68 N4cd3f783d9b342019b19732521fc61b7 rdf:first sg:person.010152520633.58
69 rdf:rest Nffe933578dbb40b99191289030c7702e
70 N543754c3c3054e1fa8799c43c5a9a2e3 rdf:first sg:person.010543570163.13
71 rdf:rest Nf01a0450785f470ca94bc2e5da0df297
72 N604aa033567541a6a904a089304ddb6a rdf:first N257c6db51e7a4dbeb33f638bb46184a3
73 rdf:rest N9eeffd28785c4c9f9948c097232576da
74 N6c83f6dc3fa74934a35583abbe032f98 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N9eeffd28785c4c9f9948c097232576da rdf:first Ne52cc4f03cb546d58b23a0afc2734358
77 rdf:rest rdf:nil
78 Nd45e3de98b9140f7818e18efea867ac7 schema:name dimensions_id
79 schema:value pub.1103771347
80 rdf:type schema:PropertyValue
81 Nddfdaabd442f43ec9eb03b0f89ce50bd schema:isbn 978-3-319-90529-7
82 978-3-319-90530-3
83 schema:name Computer Science – Theory and Applications
84 rdf:type schema:Book
85 Ne52cc4f03cb546d58b23a0afc2734358 schema:familyName Podolskii
86 schema:givenName Vladimir V.
87 rdf:type schema:Person
88 Nf01a0450785f470ca94bc2e5da0df297 rdf:first sg:person.016214735032.21
89 rdf:rest rdf:nil
90 Nffe933578dbb40b99191289030c7702e rdf:first sg:person.015611460437.34
91 rdf:rest N19977948934d4d3b9d422e5211fa9a1d
92 anzsrc-for:07 schema:inDefinedTermSet anzsrc-for:
93 schema:name Agricultural and Veterinary Sciences
94 rdf:type schema:DefinedTerm
95 anzsrc-for:0705 schema:inDefinedTermSet anzsrc-for:
96 schema:name Forestry Sciences
97 rdf:type schema:DefinedTerm
98 sg:person.010152520633.58 schema:affiliation grid-institutes:grid.7372.1
99 schema:familyName Gascón
100 schema:givenName Adrià
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010152520633.58
102 rdf:type schema:Person
103 sg:person.010543570163.13 schema:affiliation grid-institutes:grid.5836.8
104 schema:familyName Reh
105 schema:givenName Carl Philipp
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010543570163.13
107 rdf:type schema:Person
108 sg:person.015611460437.34 schema:affiliation grid-institutes:grid.5836.8
109 schema:familyName Lohrey
110 schema:givenName Markus
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015611460437.34
112 rdf:type schema:Person
113 sg:person.016214735032.21 schema:affiliation grid-institutes:grid.5836.8
114 schema:familyName Sieber
115 schema:givenName Kurt
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016214735032.21
117 rdf:type schema:Person
118 sg:person.016240662443.33 schema:affiliation grid-institutes:grid.7704.4
119 schema:familyName Maneth
120 schema:givenName Sebastian
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
122 rdf:type schema:Person
123 grid-institutes:grid.5836.8 schema:alternateName Universität Siegen, Siegen, Germany
124 schema:name Universität Siegen, Siegen, Germany
125 rdf:type schema:Organization
126 grid-institutes:grid.7372.1 schema:alternateName Warwick University and Alan Turing Institute, Warwick, UK
127 schema:name Warwick University and Alan Turing Institute, Warwick, UK
128 rdf:type schema:Organization
129 grid-institutes:grid.7704.4 schema:alternateName Universität Bremen, Bremen, Germany
130 schema:name Universität Bremen, Bremen, Germany
131 rdf:type schema:Organization
 




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


...