Exact XML Type Checking in Polynomial Time View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Sebastian Maneth , Thomas Perst , Helmut Seidl

ABSTRACT

Stay macro tree transducers (smtts) are an expressive formalism for reasoning about XSLT-like document transformations. Here, we consider the exact type checking problem for smtts. While the problem is decidable, the involved technique of inverse type inference is known to have exponential worst-case complexity (already for top-down transformations without parameters). We present a new adaptive type checking algorithm based on forward type inference through exact characterizations of output languages. The new algorithm correctly type-checks all call-by-value smtts. Given that the output type is specified by a deterministic automaton, the algorithm is polynomial-time whenever the transducer uses only few parameters and visits every input node only constantly often. Our new approach can also be generalized from smtts to stay macro forest transducers which additionally support concatenation as built-in output operation. More... »

PAGES

254-268

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11965893_18

DOI

http://dx.doi.org/10.1007/11965893_18

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National ICT Australia and School of Computer Science and Engineering, UNSW, Sydney Research Lab, Sydney, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1005.4", 
          "name": [
            "National ICT Australia and School of Computer Science and Engineering, UNSW, Sydney Research Lab, Sydney, 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": "Technische Universit\u00e4t M\u00fcnchen, Garching, Germany", 
          "id": "http://www.grid.ac/institutes/grid.6936.a", 
          "name": [
            "Technische Universit\u00e4t M\u00fcnchen, Garching, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Perst", 
        "givenName": "Thomas", 
        "id": "sg:person.012211617651.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012211617651.18"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technische Universit\u00e4t M\u00fcnchen, Garching, Germany", 
          "id": "http://www.grid.ac/institutes/grid.6936.a", 
          "name": [
            "Technische Universit\u00e4t M\u00fcnchen, Garching, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Seidl", 
        "givenName": "Helmut", 
        "id": "sg:person.0600150505.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0600150505.21"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "Stay macro tree transducers (smtts) are an expressive formalism for reasoning about XSLT-like document transformations. Here, we consider the exact type checking problem for smtts. While the problem is decidable, the involved technique of inverse type inference is known to have exponential worst-case complexity (already for top-down transformations without parameters). We present a new adaptive type checking algorithm based on forward type inference through exact characterizations of output languages. The new algorithm correctly type-checks all call-by-value smtts. Given that the output type is specified by a deterministic automaton, the algorithm is polynomial-time whenever the transducer uses only few parameters and visits every input node only constantly often. Our new approach can also be generalized from smtts to stay macro forest transducers which additionally support concatenation as built-in output operation.", 
    "editor": [
      {
        "familyName": "Schwentick", 
        "givenName": "Thomas", 
        "type": "Person"
      }, 
      {
        "familyName": "Suciu", 
        "givenName": "Dan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11965893_18", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-69269-0", 
        "978-3-540-69270-6"
      ], 
      "name": "Database Theory \u2013 ICDT 2007", 
      "type": "Book"
    }, 
    "keywords": [
      "type inference", 
      "exponential worst-case complexity", 
      "worst-case complexity", 
      "type checking algorithm", 
      "expressive formalism", 
      "document transformation", 
      "checking algorithm", 
      "type checking", 
      "polynomial time", 
      "new algorithm", 
      "input nodes", 
      "output operations", 
      "output type", 
      "algorithm", 
      "output language", 
      "macro forest transducers", 
      "involved techniques", 
      "new approach", 
      "exact characterization", 
      "tree transducers", 
      "checking", 
      "inference", 
      "macro tree transducers", 
      "nodes", 
      "complexity", 
      "language", 
      "automata", 
      "concatenation", 
      "exact type", 
      "deterministic automata", 
      "operation", 
      "technique", 
      "formalism", 
      "calls", 
      "time", 
      "transformation", 
      "types", 
      "parameters", 
      "transducer", 
      "characterization", 
      "visits", 
      "problem", 
      "approach", 
      "XSLT-like document transformations", 
      "smtts", 
      "inverse type inference", 
      "new adaptive type checking algorithm", 
      "adaptive type checking algorithm", 
      "forward type inference", 
      "value smtts", 
      "forest transducers", 
      "Exact XML Type Checking", 
      "XML Type Checking"
    ], 
    "name": "Exact XML Type Checking in Polynomial Time", 
    "pagination": "254-268", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004130934"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11965893_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11965893_18", 
      "https://app.dimensions.ai/details/publication/pub.1004130934"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T19:03", 
    "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_75.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11965893_18"
  }
]
 

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/11965893_18'

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/11965893_18'

Turtle is a human-readable linked data format.

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

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

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


 

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

135 TRIPLES      23 PREDICATES      79 URIs      72 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11965893_18 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ncb2c1f00c329467f9f401f3be9a98419
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description Stay macro tree transducers (smtts) are an expressive formalism for reasoning about XSLT-like document transformations. Here, we consider the exact type checking problem for smtts. While the problem is decidable, the involved technique of inverse type inference is known to have exponential worst-case complexity (already for top-down transformations without parameters). We present a new adaptive type checking algorithm based on forward type inference through exact characterizations of output languages. The new algorithm correctly type-checks all call-by-value smtts. Given that the output type is specified by a deterministic automaton, the algorithm is polynomial-time whenever the transducer uses only few parameters and visits every input node only constantly often. Our new approach can also be generalized from smtts to stay macro forest transducers which additionally support concatenation as built-in output operation.
7 schema:editor N3d51ff8e7ba54ae39a4bf5325c1f6f1e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nf6a10a62e73047df9949b1035bb26eba
12 schema:keywords Exact XML Type Checking
13 XML Type Checking
14 XSLT-like document transformations
15 adaptive type checking algorithm
16 algorithm
17 approach
18 automata
19 calls
20 characterization
21 checking
22 checking algorithm
23 complexity
24 concatenation
25 deterministic automata
26 document transformation
27 exact characterization
28 exact type
29 exponential worst-case complexity
30 expressive formalism
31 forest transducers
32 formalism
33 forward type inference
34 inference
35 input nodes
36 inverse type inference
37 involved techniques
38 language
39 macro forest transducers
40 macro tree transducers
41 new adaptive type checking algorithm
42 new algorithm
43 new approach
44 nodes
45 operation
46 output language
47 output operations
48 output type
49 parameters
50 polynomial time
51 problem
52 smtts
53 technique
54 time
55 transducer
56 transformation
57 tree transducers
58 type checking
59 type checking algorithm
60 type inference
61 types
62 value smtts
63 visits
64 worst-case complexity
65 schema:name Exact XML Type Checking in Polynomial Time
66 schema:pagination 254-268
67 schema:productId N06dfc0f7585c4f45b618270332301698
68 N49088bab0fdb4ef296ff79088b615f28
69 schema:publisher N1508a80309ef4f279b695aab309ea16b
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004130934
71 https://doi.org/10.1007/11965893_18
72 schema:sdDatePublished 2021-11-01T19:03
73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
74 schema:sdPublisher Nd5f4334a221641428b06196dbaa9e712
75 schema:url https://doi.org/10.1007/11965893_18
76 sgo:license sg:explorer/license/
77 sgo:sdDataset chapters
78 rdf:type schema:Chapter
79 N06dfc0f7585c4f45b618270332301698 schema:name doi
80 schema:value 10.1007/11965893_18
81 rdf:type schema:PropertyValue
82 N1508a80309ef4f279b695aab309ea16b schema:name Springer Nature
83 rdf:type schema:Organisation
84 N3d51ff8e7ba54ae39a4bf5325c1f6f1e rdf:first N9b9b6cb1ebba43549d4ba4a6d38ab0f2
85 rdf:rest N79a0a342896443cb8f44d396f6381d08
86 N49088bab0fdb4ef296ff79088b615f28 schema:name dimensions_id
87 schema:value pub.1004130934
88 rdf:type schema:PropertyValue
89 N544e6771a7964c618bbfdd8038c5fd6d rdf:first sg:person.0600150505.21
90 rdf:rest rdf:nil
91 N79a0a342896443cb8f44d396f6381d08 rdf:first Nade052aa38a64ccbab0e245f7f0b2e75
92 rdf:rest rdf:nil
93 N9b9b6cb1ebba43549d4ba4a6d38ab0f2 schema:familyName Schwentick
94 schema:givenName Thomas
95 rdf:type schema:Person
96 Nade052aa38a64ccbab0e245f7f0b2e75 schema:familyName Suciu
97 schema:givenName Dan
98 rdf:type schema:Person
99 Nb6da2e08f0f64adda389d726ba19c3c8 rdf:first sg:person.012211617651.18
100 rdf:rest N544e6771a7964c618bbfdd8038c5fd6d
101 Ncb2c1f00c329467f9f401f3be9a98419 rdf:first sg:person.016240662443.33
102 rdf:rest Nb6da2e08f0f64adda389d726ba19c3c8
103 Nd5f4334a221641428b06196dbaa9e712 schema:name Springer Nature - SN SciGraph project
104 rdf:type schema:Organization
105 Nf6a10a62e73047df9949b1035bb26eba schema:isbn 978-3-540-69269-0
106 978-3-540-69270-6
107 schema:name Database Theory – ICDT 2007
108 rdf:type schema:Book
109 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
110 schema:name Information and Computing Sciences
111 rdf:type schema:DefinedTerm
112 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
113 schema:name Computation Theory and Mathematics
114 rdf:type schema:DefinedTerm
115 sg:person.012211617651.18 schema:affiliation grid-institutes:grid.6936.a
116 schema:familyName Perst
117 schema:givenName Thomas
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012211617651.18
119 rdf:type schema:Person
120 sg:person.016240662443.33 schema:affiliation grid-institutes:grid.1005.4
121 schema:familyName Maneth
122 schema:givenName Sebastian
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
124 rdf:type schema:Person
125 sg:person.0600150505.21 schema:affiliation grid-institutes:grid.6936.a
126 schema:familyName Seidl
127 schema:givenName Helmut
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0600150505.21
129 rdf:type schema:Person
130 grid-institutes:grid.1005.4 schema:alternateName National ICT Australia and School of Computer Science and Engineering, UNSW, Sydney Research Lab, Sydney, Australia
131 schema:name National ICT Australia and School of Computer Science and Engineering, UNSW, Sydney Research Lab, Sydney, Australia
132 rdf:type schema:Organization
133 grid-institutes:grid.6936.a schema:alternateName Technische Universität München, Garching, Germany
134 schema:name Technische Universität München, Garching, Germany
135 rdf:type schema:Organization
 




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


...