Tree Automata and XPath on Compressed Trees View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Markus Lohrey , Sebastian Maneth

ABSTRACT

The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts of a tree. Several completeness results for the classes NL, P, and PSPACE are obtained. Finally, the complexity of the XPath evaluation problem on trees that are compressed via straight-line context-free tree grammars is investigated. More... »

PAGES

225-237

Book

TITLE

Implementation and Application of Automata

ISBN

978-3-540-31023-5
978-3-540-33097-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11605157_19

DOI

http://dx.doi.org/10.1007/11605157_19

DIMENSIONS

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


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": "FMI, University of Stuttgaert, Germany", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "FMI, University of Stuttgaert, 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": "Facult\u00e9 I & C, EPFL, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5333.6", 
          "name": [
            "Facult\u00e9 I & C, EPFL, Switzerland"
          ], 
          "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"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts of a tree. Several completeness results for the classes NL, P, and PSPACE are obtained. Finally, the complexity of the XPath evaluation problem on trees that are compressed via straight-line context-free tree grammars is investigated.", 
    "editor": [
      {
        "familyName": "Farr\u00e9", 
        "givenName": "Jacques", 
        "type": "Person"
      }, 
      {
        "familyName": "Litovsky", 
        "givenName": "Igor", 
        "type": "Person"
      }, 
      {
        "familyName": "Schmitz", 
        "givenName": "Sylvain", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11605157_19", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-31023-5", 
        "978-3-540-33097-4"
      ], 
      "name": "Implementation and Application of Automata", 
      "type": "Book"
    }, 
    "keywords": [
      "XPath evaluation problem", 
      "tree automata", 
      "context-free tree grammars", 
      "tree grammars", 
      "compressed trees", 
      "identical subtrees", 
      "straight-line context-free tree grammars", 
      "evaluation problem", 
      "complexity", 
      "membership problem", 
      "automata", 
      "trees", 
      "grammar", 
      "classes NL", 
      "PSPACE", 
      "XPath", 
      "representation", 
      "DAG", 
      "subtrees", 
      "completeness", 
      "part", 
      "NL", 
      "intermediate part", 
      "problem", 
      "identical intermediate parts"
    ], 
    "name": "Tree Automata and XPath on Compressed Trees", 
    "pagination": "225-237", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014036381"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11605157_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11605157_19", 
      "https://app.dimensions.ai/details/publication/pub.1014036381"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:12", 
    "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/chapter/chapter_214.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11605157_19"
  }
]
 

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/11605157_19'

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/11605157_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11605157_19'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11605157_19'


 

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

105 TRIPLES      23 PREDICATES      51 URIs      44 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11605157_19 schema:about anzsrc-for:06
2 anzsrc-for:0607
3 schema:author Nd2c5b6c8d7324a65b33270f0345fa0f1
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts of a tree. Several completeness results for the classes NL, P, and PSPACE are obtained. Finally, the complexity of the XPath evaluation problem on trees that are compressed via straight-line context-free tree grammars is investigated.
7 schema:editor N1bc3478c20054cd4aa6dffced25fb0e7
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne56bf978fba54daf9514f67c96b6a7c1
12 schema:keywords DAG
13 NL
14 PSPACE
15 XPath
16 XPath evaluation problem
17 automata
18 classes NL
19 completeness
20 complexity
21 compressed trees
22 context-free tree grammars
23 evaluation problem
24 grammar
25 identical intermediate parts
26 identical subtrees
27 intermediate part
28 membership problem
29 part
30 problem
31 representation
32 straight-line context-free tree grammars
33 subtrees
34 tree automata
35 tree grammars
36 trees
37 schema:name Tree Automata and XPath on Compressed Trees
38 schema:pagination 225-237
39 schema:productId N4fc528a997c94142922cc90b97ad7c02
40 Nfd99322cb5d14c18bd11d370fbfdfa99
41 schema:publisher N509d8caa2d964803b2332432ef9f3366
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014036381
43 https://doi.org/10.1007/11605157_19
44 schema:sdDatePublished 2022-01-01T19:12
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher Ndd7cc33071974df5ac141829ee1176f9
47 schema:url https://doi.org/10.1007/11605157_19
48 sgo:license sg:explorer/license/
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N0b3748d627484b259ab95ce29e7a1b42 rdf:first N5fc40d542d474891ae9033ee5facab7f
52 rdf:rest rdf:nil
53 N1bc3478c20054cd4aa6dffced25fb0e7 rdf:first N649c235ad22f464f9638c4fd164f824e
54 rdf:rest N98c07eb5853d44c69c5359368c8f176d
55 N4fc528a997c94142922cc90b97ad7c02 schema:name dimensions_id
56 schema:value pub.1014036381
57 rdf:type schema:PropertyValue
58 N509d8caa2d964803b2332432ef9f3366 schema:name Springer Nature
59 rdf:type schema:Organisation
60 N5fc40d542d474891ae9033ee5facab7f schema:familyName Schmitz
61 schema:givenName Sylvain
62 rdf:type schema:Person
63 N649c235ad22f464f9638c4fd164f824e schema:familyName Farré
64 schema:givenName Jacques
65 rdf:type schema:Person
66 N98c07eb5853d44c69c5359368c8f176d rdf:first Nb7fc3397b6ab4abe839280ddf87342c0
67 rdf:rest N0b3748d627484b259ab95ce29e7a1b42
68 Nb7fc3397b6ab4abe839280ddf87342c0 schema:familyName Litovsky
69 schema:givenName Igor
70 rdf:type schema:Person
71 Nd2c5b6c8d7324a65b33270f0345fa0f1 rdf:first sg:person.015611460437.34
72 rdf:rest Nfece29861df343a2b0e9024000b570fb
73 Ndd7cc33071974df5ac141829ee1176f9 schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 Ne56bf978fba54daf9514f67c96b6a7c1 schema:isbn 978-3-540-31023-5
76 978-3-540-33097-4
77 schema:name Implementation and Application of Automata
78 rdf:type schema:Book
79 Nfd99322cb5d14c18bd11d370fbfdfa99 schema:name doi
80 schema:value 10.1007/11605157_19
81 rdf:type schema:PropertyValue
82 Nfece29861df343a2b0e9024000b570fb rdf:first sg:person.016240662443.33
83 rdf:rest rdf:nil
84 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
85 schema:name Biological Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0607 schema:inDefinedTermSet anzsrc-for:
88 schema:name Plant Biology
89 rdf:type schema:DefinedTerm
90 sg:person.015611460437.34 schema:affiliation grid-institutes:None
91 schema:familyName Lohrey
92 schema:givenName Markus
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015611460437.34
94 rdf:type schema:Person
95 sg:person.016240662443.33 schema:affiliation grid-institutes:grid.5333.6
96 schema:familyName Maneth
97 schema:givenName Sebastian
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
99 rdf:type schema:Person
100 grid-institutes:None schema:alternateName FMI, University of Stuttgaert, Germany
101 schema:name FMI, University of Stuttgaert, Germany
102 rdf:type schema:Organization
103 grid-institutes:grid.5333.6 schema:alternateName Faculté I & C, EPFL, Switzerland
104 schema:name Faculté I & C, EPFL, Switzerland
105 rdf:type schema:Organization
 




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


...