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": "2021-12-01T20:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_59.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 N3e866e994f0848d1acface85d3d6d824
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 Na7fd265d73594faeac4981f03b1c9bd3
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N4dc8936e49314e1fb33f2b77fbc27f9a
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 Na9b922fc223d4ade808a4575472f113b
40 Nb074ef893a2f4c0eb3b7791fc25d0a17
41 schema:publisher N23da48d720ca48dbb234c2343efa62fe
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014036381
43 https://doi.org/10.1007/11605157_19
44 schema:sdDatePublished 2021-12-01T20:12
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher N2d8d4af470874171a2f5a0c4834f64a0
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 N23bcdeb71796473da3452c5cff0504b8 schema:familyName Schmitz
52 schema:givenName Sylvain
53 rdf:type schema:Person
54 N23da48d720ca48dbb234c2343efa62fe schema:name Springer Nature
55 rdf:type schema:Organisation
56 N2d8d4af470874171a2f5a0c4834f64a0 schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 N37bd03491fae49538edf774142aa6f39 schema:familyName Farré
59 schema:givenName Jacques
60 rdf:type schema:Person
61 N3e866e994f0848d1acface85d3d6d824 rdf:first sg:person.015611460437.34
62 rdf:rest Nb8aa87b5f8ef4bca836d4f80a9fa6ee7
63 N4dc8936e49314e1fb33f2b77fbc27f9a schema:isbn 978-3-540-31023-5
64 978-3-540-33097-4
65 schema:name Implementation and Application of Automata
66 rdf:type schema:Book
67 N6e5df1647a7b4b28bc313f782e5e44e8 rdf:first N23bcdeb71796473da3452c5cff0504b8
68 rdf:rest rdf:nil
69 N70842393853442d19e8788260275c89e rdf:first Ndd8c6c4d750341a3b6f543602a566e18
70 rdf:rest N6e5df1647a7b4b28bc313f782e5e44e8
71 Na7fd265d73594faeac4981f03b1c9bd3 rdf:first N37bd03491fae49538edf774142aa6f39
72 rdf:rest N70842393853442d19e8788260275c89e
73 Na9b922fc223d4ade808a4575472f113b schema:name doi
74 schema:value 10.1007/11605157_19
75 rdf:type schema:PropertyValue
76 Nb074ef893a2f4c0eb3b7791fc25d0a17 schema:name dimensions_id
77 schema:value pub.1014036381
78 rdf:type schema:PropertyValue
79 Nb8aa87b5f8ef4bca836d4f80a9fa6ee7 rdf:first sg:person.016240662443.33
80 rdf:rest rdf:nil
81 Ndd8c6c4d750341a3b6f543602a566e18 schema:familyName Litovsky
82 schema:givenName Igor
83 rdf:type schema:Person
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)


...