Tree Transducers and Tree Compressions View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Sebastian Maneth , Giorgio Busatto

ABSTRACT

A tree can be compressed into a DAG by sharing common subtrees. The resulting DAG is at most exponentially smaller than the original tree. Consider an attribute grammar that generates trees as output. It is well known that, given an input tree s, a DAG representation of the corresponding output tree can be computed in time linear in the size of s. A more powerful way of tree compression is to allow the sharing of tree patterns, i.e., internal parts of the tree. The resulting “sharing graph” is at most double-exponentially smaller than the original tree. Consider a macro tree transducer and an input tree s. The main result is that a sharing graph representation of the corresponding output tree can be computed in time linear in the size of s. A similar result holds for macro forest transducers which translate unranked forests, i.e., natural representations of XML documents. More... »

PAGES

363-377

Book

TITLE

Foundations of Software Science and Computation Structures

ISBN

978-3-540-21298-0
978-3-540-24727-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24727-2_26

DOI

http://dx.doi.org/10.1007/978-3-540-24727-2_26

DIMENSIONS

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


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": "EPF Lausanne, School of Computer and Communication Sciences", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "EPF Lausanne, School of Computer and Communication Sciences"
          ], 
          "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": "Department f\u00fcr Informatik, Universit\u00e4t Oldenburg", 
          "id": "http://www.grid.ac/institutes/grid.5560.6", 
          "name": [
            "Department f\u00fcr Informatik, Universit\u00e4t Oldenburg"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Busatto", 
        "givenName": "Giorgio", 
        "id": "sg:person.010376065260.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010376065260.68"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "A tree can be compressed into a DAG by sharing common subtrees. The resulting DAG is at most exponentially smaller than the original tree. Consider an attribute grammar that generates trees as output. It is well known that, given an input tree s, a DAG representation of the corresponding output tree can be computed in time linear in the size of s. A more powerful way of tree compression is to allow the sharing of tree patterns, i.e., internal parts of the tree. The resulting \u201csharing graph\u201d is at most double-exponentially smaller than the original tree. Consider a macro tree transducer and an input tree s. The main result is that a sharing graph representation of the corresponding output tree can be computed in time linear in the size of s. A similar result holds for macro forest transducers which translate unranked forests, i.e., natural representations of XML documents.", 
    "editor": [
      {
        "familyName": "Walukiewicz", 
        "givenName": "Igor", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24727-2_26", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-21298-0", 
        "978-3-540-24727-2"
      ], 
      "name": "Foundations of Software Science and Computation Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "tree compression", 
      "output tree", 
      "XML documents", 
      "attribute grammars", 
      "graph representation", 
      "DAG representation", 
      "tree patterns", 
      "common subtrees", 
      "original tree", 
      "natural representation", 
      "tree transducers", 
      "macro forest transducers", 
      "DAG", 
      "representation", 
      "powerful way", 
      "trees", 
      "sharing", 
      "graph", 
      "subtrees", 
      "compression", 
      "macro tree transducers", 
      "documents", 
      "grammar", 
      "output", 
      "time", 
      "way", 
      "results", 
      "size", 
      "main results", 
      "part", 
      "patterns", 
      "internal part", 
      "forest", 
      "transducer", 
      "tree S", 
      "similar results", 
      "s.", 
      "input tree s", 
      "corresponding output tree", 
      "input tree s.", 
      "tree s.", 
      "forest transducers", 
      "unranked forests"
    ], 
    "name": "Tree Transducers and Tree Compressions", 
    "pagination": "363-377", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1006395804"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24727-2_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24727-2_26", 
      "https://app.dimensions.ai/details/publication/pub.1006395804"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:46", 
    "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_118.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-24727-2_26"
  }
]
 

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-540-24727-2_26'

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-540-24727-2_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24727-2_26'

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-540-24727-2_26'


 

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

113 TRIPLES      23 PREDICATES      69 URIs      62 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24727-2_26 schema:about anzsrc-for:07
2 anzsrc-for:0705
3 schema:author N65e28a5599884eedbb5feeb1d41e552c
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description A tree can be compressed into a DAG by sharing common subtrees. The resulting DAG is at most exponentially smaller than the original tree. Consider an attribute grammar that generates trees as output. It is well known that, given an input tree s, a DAG representation of the corresponding output tree can be computed in time linear in the size of s. A more powerful way of tree compression is to allow the sharing of tree patterns, i.e., internal parts of the tree. The resulting “sharing graph” is at most double-exponentially smaller than the original tree. Consider a macro tree transducer and an input tree s. The main result is that a sharing graph representation of the corresponding output tree can be computed in time linear in the size of s. A similar result holds for macro forest transducers which translate unranked forests, i.e., natural representations of XML documents.
7 schema:editor N86cb8a6f82f141dfb66c92d25be990e6
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N56f78c4d8a8c4e9da27d1bfea072027f
12 schema:keywords DAG
13 DAG representation
14 XML documents
15 attribute grammars
16 common subtrees
17 compression
18 corresponding output tree
19 documents
20 forest
21 forest transducers
22 grammar
23 graph
24 graph representation
25 input tree s
26 input tree s.
27 internal part
28 macro forest transducers
29 macro tree transducers
30 main results
31 natural representation
32 original tree
33 output
34 output tree
35 part
36 patterns
37 powerful way
38 representation
39 results
40 s.
41 sharing
42 similar results
43 size
44 subtrees
45 time
46 transducer
47 tree S
48 tree compression
49 tree patterns
50 tree s.
51 tree transducers
52 trees
53 unranked forests
54 way
55 schema:name Tree Transducers and Tree Compressions
56 schema:pagination 363-377
57 schema:productId N6c79f97a0f7849d69f6c81471409d9da
58 N8ba2a21fbad84fa38774bcf7238facad
59 schema:publisher Nc1db6632e6594adb8193f9e3e7e42c2c
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006395804
61 https://doi.org/10.1007/978-3-540-24727-2_26
62 schema:sdDatePublished 2021-11-01T18:46
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N5437b925a29a4c9cb0214d8076848c6a
65 schema:url https://doi.org/10.1007/978-3-540-24727-2_26
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N5437b925a29a4c9cb0214d8076848c6a schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N56f78c4d8a8c4e9da27d1bfea072027f schema:isbn 978-3-540-21298-0
72 978-3-540-24727-2
73 schema:name Foundations of Software Science and Computation Structures
74 rdf:type schema:Book
75 N65e28a5599884eedbb5feeb1d41e552c rdf:first sg:person.016240662443.33
76 rdf:rest N9d3624a0965447e79cb72968ff91badd
77 N6c79f97a0f7849d69f6c81471409d9da schema:name doi
78 schema:value 10.1007/978-3-540-24727-2_26
79 rdf:type schema:PropertyValue
80 N86cb8a6f82f141dfb66c92d25be990e6 rdf:first Nd983469a31ff469ea596984be92c9d42
81 rdf:rest rdf:nil
82 N8ba2a21fbad84fa38774bcf7238facad schema:name dimensions_id
83 schema:value pub.1006395804
84 rdf:type schema:PropertyValue
85 N9d3624a0965447e79cb72968ff91badd rdf:first sg:person.010376065260.68
86 rdf:rest rdf:nil
87 Nc1db6632e6594adb8193f9e3e7e42c2c schema:name Springer Nature
88 rdf:type schema:Organisation
89 Nd983469a31ff469ea596984be92c9d42 schema:familyName Walukiewicz
90 schema:givenName Igor
91 rdf:type schema:Person
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.010376065260.68 schema:affiliation grid-institutes:grid.5560.6
99 schema:familyName Busatto
100 schema:givenName Giorgio
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010376065260.68
102 rdf:type schema:Person
103 sg:person.016240662443.33 schema:affiliation grid-institutes:None
104 schema:familyName Maneth
105 schema:givenName Sebastian
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
107 rdf:type schema:Person
108 grid-institutes:None schema:alternateName EPF Lausanne, School of Computer and Communication Sciences
109 schema:name EPF Lausanne, School of Computer and Communication Sciences
110 rdf:type schema:Organization
111 grid-institutes:grid.5560.6 schema:alternateName Department für Informatik, Universität Oldenburg
112 schema:name Department für Informatik, Universität Oldenburg
113 rdf:type schema:Organization
 




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


...