The Complexity of Compositions of Deterministic Tree Transducers View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-12-16

AUTHORS

Sebastian Maneth

ABSTRACT

Macro tree transducers can simulate most models of tree transducers (e.g., top-down and bottom-up tree transducers, attribute grammars, and pebble tree transducers which, in turn, can simulate all known models of XML transformers). The string languages generated by compositions of macro tree transducers (obtained by reading the leaves of the output trees) form a large class which contains, e.g., the IO hierarchy and the EDT0L control hierarchy. Consider an arbitrary composition τ of (deterministic) macro tree transducers. How dificult is it, for a given input tree s, to compute the translation t = τ (s)? It is shown that this problem can be solved (on a RAM) in time linear in the sum of the sizes of s and t. Moreover, the problem to determine, for a given t of size n, whether or not there is an input tree s such that t = τ (s) is in DSPACE(n); this means that output languages of compositions of macro tree transducers are deterministic context-sensitive. The involved technique of compressing intermediate results of the composition, also gives a new proof of the fact that the finiteness problem for τ ’s range is decidable. More... »

PAGES

265-276

Book

TITLE

FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science

ISBN

978-3-540-00225-3
978-3-540-36206-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-36206-1_24

DOI

http://dx.doi.org/10.1007/3-540-36206-1_24

DIMENSIONS

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


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": "LIACS, Leiden University, P.O.Box 9512, 2300, RA Leiden, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.5132.5", 
          "name": [
            "LIACS, Leiden University, P.O.Box 9512, 2300, RA Leiden, The Netherlands"
          ], 
          "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": "2002-12-16", 
    "datePublishedReg": "2002-12-16", 
    "description": "Macro tree transducers can simulate most models of tree transducers (e.g., top-down and bottom-up tree transducers, attribute grammars, and pebble tree transducers which, in turn, can simulate all known models of XML transformers). The string languages generated by compositions of macro tree transducers (obtained by reading the leaves of the output trees) form a large class which contains, e.g., the IO hierarchy and the EDT0L control hierarchy. Consider an arbitrary composition \u03c4 of (deterministic) macro tree transducers. How dificult is it, for a given input tree s, to compute the translation t = \u03c4 (s)? It is shown that this problem can be solved (on a RAM) in time linear in the sum of the sizes of s and t. Moreover, the problem to determine, for a given t of size n, whether or not there is an input tree s such that t = \u03c4 (s) is in DSPACE(n); this means that output languages of compositions of macro tree transducers are deterministic context-sensitive. The involved technique of compressing intermediate results of the composition, also gives a new proof of the fact that the finiteness problem for \u03c4 \u2019s range is decidable.", 
    "editor": [
      {
        "familyName": "Agrawal", 
        "givenName": "Manindra", 
        "type": "Person"
      }, 
      {
        "familyName": "Seth", 
        "givenName": "Anil", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-36206-1_24", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-00225-3", 
        "978-3-540-36206-7"
      ], 
      "name": "FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science", 
      "type": "Book"
    }, 
    "keywords": [
      "most models", 
      "string languages", 
      "large class", 
      "class", 
      "hierarchy", 
      "control hierarchy", 
      "problem", 
      "sum", 
      "size n", 
      "involved techniques", 
      "intermediate results", 
      "new proof", 
      "proof", 
      "finiteness problem", 
      "tree transducers", 
      "transducer", 
      "model", 
      "language", 
      "dificult", 
      "tree S", 
      "time", 
      "size", 
      "output language", 
      "technique", 
      "results", 
      "fact", 
      "range", 
      "complexity", 
      "macro tree transducers", 
      "composition", 
      "IO hierarchy", 
      "EDT0L control hierarchy", 
      "arbitrary composition \u03c4", 
      "composition \u03c4", 
      "input tree s", 
      "translation T", 
      "complexity of composition", 
      "Deterministic Tree Transducers"
    ], 
    "name": "The Complexity of Compositions of Deterministic Tree Transducers", 
    "pagination": "265-276", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1033172877"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-36206-1_24"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-36206-1_24", 
      "https://app.dimensions.ai/details/publication/pub.1033172877"
    ], 
    "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_131.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-36206-1_24"
  }
]
 

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/3-540-36206-1_24'

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/3-540-36206-1_24'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-36206-1_24'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-36206-1_24'


 

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

103 TRIPLES      23 PREDICATES      63 URIs      56 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-36206-1_24 schema:about anzsrc-for:06
2 anzsrc-for:0607
3 schema:author N75750d39496e4d71bb0ed253d1cf3af9
4 schema:datePublished 2002-12-16
5 schema:datePublishedReg 2002-12-16
6 schema:description Macro tree transducers can simulate most models of tree transducers (e.g., top-down and bottom-up tree transducers, attribute grammars, and pebble tree transducers which, in turn, can simulate all known models of XML transformers). The string languages generated by compositions of macro tree transducers (obtained by reading the leaves of the output trees) form a large class which contains, e.g., the IO hierarchy and the EDT0L control hierarchy. Consider an arbitrary composition τ of (deterministic) macro tree transducers. How dificult is it, for a given input tree s, to compute the translation t = τ (s)? It is shown that this problem can be solved (on a RAM) in time linear in the sum of the sizes of s and t. Moreover, the problem to determine, for a given t of size n, whether or not there is an input tree s such that t = τ (s) is in DSPACE(n); this means that output languages of compositions of macro tree transducers are deterministic context-sensitive. The involved technique of compressing intermediate results of the composition, also gives a new proof of the fact that the finiteness problem for τ ’s range is decidable.
7 schema:editor N818aae14e81547a2ba99ca4db510597c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N9d77463676264d6fbd198632f418064c
12 schema:keywords Deterministic Tree Transducers
13 EDT0L control hierarchy
14 IO hierarchy
15 arbitrary composition τ
16 class
17 complexity
18 complexity of composition
19 composition
20 composition τ
21 control hierarchy
22 dificult
23 fact
24 finiteness problem
25 hierarchy
26 input tree s
27 intermediate results
28 involved techniques
29 language
30 large class
31 macro tree transducers
32 model
33 most models
34 new proof
35 output language
36 problem
37 proof
38 range
39 results
40 size
41 size n
42 string languages
43 sum
44 technique
45 time
46 transducer
47 translation T
48 tree S
49 tree transducers
50 schema:name The Complexity of Compositions of Deterministic Tree Transducers
51 schema:pagination 265-276
52 schema:productId N38ed4ae03ad74bacbc69016190abd32d
53 N88c6637f5d404eec945f9eb051cde32b
54 schema:publisher N45f7c1992d15430a906e6773185c8b97
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033172877
56 https://doi.org/10.1007/3-540-36206-1_24
57 schema:sdDatePublished 2021-11-01T18:47
58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
59 schema:sdPublisher N7e46931dbd144daf8960e8914992ee30
60 schema:url https://doi.org/10.1007/3-540-36206-1_24
61 sgo:license sg:explorer/license/
62 sgo:sdDataset chapters
63 rdf:type schema:Chapter
64 N38ed4ae03ad74bacbc69016190abd32d schema:name dimensions_id
65 schema:value pub.1033172877
66 rdf:type schema:PropertyValue
67 N45f7c1992d15430a906e6773185c8b97 schema:name Springer Nature
68 rdf:type schema:Organisation
69 N75750d39496e4d71bb0ed253d1cf3af9 rdf:first sg:person.016240662443.33
70 rdf:rest rdf:nil
71 N7e46931dbd144daf8960e8914992ee30 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N818aae14e81547a2ba99ca4db510597c rdf:first Na7c5e63dce0b4395b0db57c46b206561
74 rdf:rest N94c373a51a8f4e3c8ebb0003ef70c26c
75 N88c6637f5d404eec945f9eb051cde32b schema:name doi
76 schema:value 10.1007/3-540-36206-1_24
77 rdf:type schema:PropertyValue
78 N94c373a51a8f4e3c8ebb0003ef70c26c rdf:first Nefe044f09c77478dab28be7ef072c759
79 rdf:rest rdf:nil
80 N9d77463676264d6fbd198632f418064c schema:isbn 978-3-540-00225-3
81 978-3-540-36206-7
82 schema:name FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science
83 rdf:type schema:Book
84 Na7c5e63dce0b4395b0db57c46b206561 schema:familyName Agrawal
85 schema:givenName Manindra
86 rdf:type schema:Person
87 Nefe044f09c77478dab28be7ef072c759 schema:familyName Seth
88 schema:givenName Anil
89 rdf:type schema:Person
90 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
91 schema:name Biological Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0607 schema:inDefinedTermSet anzsrc-for:
94 schema:name Plant Biology
95 rdf:type schema:DefinedTerm
96 sg:person.016240662443.33 schema:affiliation grid-institutes:grid.5132.5
97 schema:familyName Maneth
98 schema:givenName Sebastian
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
100 rdf:type schema:Person
101 grid-institutes:grid.5132.5 schema:alternateName LIACS, Leiden University, P.O.Box 9512, 2300, RA Leiden, The Netherlands
102 schema:name LIACS, Leiden University, P.O.Box 9512, 2300, RA Leiden, The Netherlands
103 rdf:type schema:Organization
 




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


...