Parameter Reduction in Grammar-Compressed Trees View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Markus Lohrey , Sebastian Maneth , Manfred Schmidt-Schauß

ABSTRACT

Trees can be conveniently compressed with linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars which are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression). It is shown that every linear straight-line context-free tree grammar can be transformed in polynomial time into a monadic (and linear) one. A tree grammar is monadic if each nonterminal uses at most one context parameter. Based on this result, a polynomial time algorithm is presented for testing whether a given nondeterministic tree automaton with sibling constraints accepts a tree given by a linear straight-line context-free tree grammar. It is shown that if tree grammars are nondeterministic or non-linear, then reducing their numbers of parameters cannot be done without an exponential blow-up in grammar size. More... »

PAGES

212-226

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-00596-1_16

DOI

http://dx.doi.org/10.1007/978-3-642-00596-1_16

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, Germany", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, 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": "NICTA and University of New South Wales, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1005.4", 
          "name": [
            "NICTA and University of New South Wales, Australia"
          ], 
          "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": "Institut f\u00fcr Informatik, Johann Wolfgang Goethe-Universit\u00e4t Frankfurt, Germany", 
          "id": "http://www.grid.ac/institutes/grid.7839.5", 
          "name": [
            "Institut f\u00fcr Informatik, Johann Wolfgang Goethe-Universit\u00e4t Frankfurt, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schmidt-Schau\u00df", 
        "givenName": "Manfred", 
        "id": "sg:person.013615656722.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013615656722.29"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "Trees can be conveniently compressed with linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars which are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression). It is shown that every linear straight-line context-free tree grammar can be transformed in polynomial time into a monadic (and linear) one. A tree grammar is monadic if each nonterminal uses at most one context parameter. Based on this result, a polynomial time algorithm is presented for testing whether a given nondeterministic tree automaton with sibling constraints accepts a tree given by a linear straight-line context-free tree grammar. It is shown that if tree grammars are nondeterministic or non-linear, then reducing their numbers of parameters cannot be done without an exponential blow-up in grammar size.", 
    "editor": [
      {
        "familyName": "de Alfaro", 
        "givenName": "Luca", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-00596-1_16", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-00595-4", 
        "978-3-642-00596-1"
      ], 
      "name": "Foundations of Software Science and Computational Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "tree grammars", 
      "development of algorithms", 
      "polynomial time algorithm", 
      "straight-line context-free tree grammars", 
      "context-free tree grammars", 
      "context parameters", 
      "polynomial time", 
      "time algorithm", 
      "grammar size", 
      "number of parameters", 
      "such grammars", 
      "algorithm", 
      "tree automata", 
      "parameter reduction", 
      "grammar", 
      "string grammars", 
      "nondeterministic tree automata", 
      "trees", 
      "automata", 
      "monadic ones", 
      "constraints", 
      "context-free string grammars", 
      "one", 
      "parameters", 
      "number", 
      "time", 
      "development", 
      "results", 
      "structure", 
      "size", 
      "reduction", 
      "linear straight-line context-free tree grammar", 
      "straight-line context-free string grammars", 
      "Grammar-Compressed Trees"
    ], 
    "name": "Parameter Reduction in Grammar-Compressed Trees", 
    "pagination": "212-226", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029599248"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-00596-1_16"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-00596-1_16", 
      "https://app.dimensions.ai/details/publication/pub.1029599248"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:47", 
    "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_142.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-00596-1_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-642-00596-1_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-642-00596-1_16'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-00596-1_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-642-00596-1_16'


 

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

114 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-00596-1_16 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N63f0ecd090434ed7937f655f63a505e0
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description Trees can be conveniently compressed with linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars which are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression). It is shown that every linear straight-line context-free tree grammar can be transformed in polynomial time into a monadic (and linear) one. A tree grammar is monadic if each nonterminal uses at most one context parameter. Based on this result, a polynomial time algorithm is presented for testing whether a given nondeterministic tree automaton with sibling constraints accepts a tree given by a linear straight-line context-free tree grammar. It is shown that if tree grammars are nondeterministic or non-linear, then reducing their numbers of parameters cannot be done without an exponential blow-up in grammar size.
7 schema:editor N84952cb7c1d4406dafa883eae05bf76b
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N019ca50c19c3478b815e18498c438a2f
12 schema:keywords Grammar-Compressed Trees
13 algorithm
14 automata
15 constraints
16 context parameters
17 context-free string grammars
18 context-free tree grammars
19 development
20 development of algorithms
21 grammar
22 grammar size
23 linear straight-line context-free tree grammar
24 monadic ones
25 nondeterministic tree automata
26 number
27 number of parameters
28 one
29 parameter reduction
30 parameters
31 polynomial time
32 polynomial time algorithm
33 reduction
34 results
35 size
36 straight-line context-free string grammars
37 straight-line context-free tree grammars
38 string grammars
39 structure
40 such grammars
41 time
42 time algorithm
43 tree automata
44 tree grammars
45 trees
46 schema:name Parameter Reduction in Grammar-Compressed Trees
47 schema:pagination 212-226
48 schema:productId N70c91cbd2a9941a09cbb39575f7e7196
49 Nb81a698394bf47078d105c09ee376301
50 schema:publisher N6926a33900104a94adcd25c771b4bda5
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029599248
52 https://doi.org/10.1007/978-3-642-00596-1_16
53 schema:sdDatePublished 2021-11-01T18:47
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher N98c0b35838fa437793d9d9efb3fd4779
56 schema:url https://doi.org/10.1007/978-3-642-00596-1_16
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N019ca50c19c3478b815e18498c438a2f schema:isbn 978-3-642-00595-4
61 978-3-642-00596-1
62 schema:name Foundations of Software Science and Computational Structures
63 rdf:type schema:Book
64 N4dbea99c7a3c4518b4e9a8478ae6a097 rdf:first sg:person.016240662443.33
65 rdf:rest N72ba7b853bf0481bbeba588f4d62a7e7
66 N63f0ecd090434ed7937f655f63a505e0 rdf:first sg:person.015611460437.34
67 rdf:rest N4dbea99c7a3c4518b4e9a8478ae6a097
68 N6926a33900104a94adcd25c771b4bda5 schema:name Springer Nature
69 rdf:type schema:Organisation
70 N70c91cbd2a9941a09cbb39575f7e7196 schema:name dimensions_id
71 schema:value pub.1029599248
72 rdf:type schema:PropertyValue
73 N72ba7b853bf0481bbeba588f4d62a7e7 rdf:first sg:person.013615656722.29
74 rdf:rest rdf:nil
75 N84952cb7c1d4406dafa883eae05bf76b rdf:first Nc25c537024834b6f829ed03bc125ff73
76 rdf:rest rdf:nil
77 N98c0b35838fa437793d9d9efb3fd4779 schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 Nb81a698394bf47078d105c09ee376301 schema:name doi
80 schema:value 10.1007/978-3-642-00596-1_16
81 rdf:type schema:PropertyValue
82 Nc25c537024834b6f829ed03bc125ff73 schema:familyName de Alfaro
83 schema:givenName Luca
84 rdf:type schema:Person
85 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
86 schema:name Mathematical Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
89 schema:name Pure Mathematics
90 rdf:type schema:DefinedTerm
91 sg:person.013615656722.29 schema:affiliation grid-institutes:grid.7839.5
92 schema:familyName Schmidt-Schauß
93 schema:givenName Manfred
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013615656722.29
95 rdf:type schema:Person
96 sg:person.015611460437.34 schema:affiliation grid-institutes:None
97 schema:familyName Lohrey
98 schema:givenName Markus
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015611460437.34
100 rdf:type schema:Person
101 sg:person.016240662443.33 schema:affiliation grid-institutes:grid.1005.4
102 schema:familyName Maneth
103 schema:givenName Sebastian
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
105 rdf:type schema:Person
106 grid-institutes:None schema:alternateName Institut für Informatik, Universität Leipzig, Germany
107 schema:name Institut für Informatik, Universität Leipzig, Germany
108 rdf:type schema:Organization
109 grid-institutes:grid.1005.4 schema:alternateName NICTA and University of New South Wales, Australia
110 schema:name NICTA and University of New South Wales, Australia
111 rdf:type schema:Organization
112 grid-institutes:grid.7839.5 schema:alternateName Institut für Informatik, Johann Wolfgang Goethe-Universität Frankfurt, Germany
113 schema:name Institut für Informatik, Johann Wolfgang Goethe-Universität Frankfurt, Germany
114 rdf:type schema:Organization
 




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


...