The time complexity of typechecking tree-walking tree transducers View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2009-04

AUTHORS

Joost Engelfriet

ABSTRACT

Tree-walking tree transducers can be typechecked in double exponential time. More generally, compositions of k tree-walking tree transducers can be typechecked in (k + 1)-fold exponential time. Consequently k-pebble tree transducers, which form a model of XML transformations and XML queries, can be typechecked in (k + 2)-fold exponential time. The results hold for both ranked and unranked trees. More... »

PAGES

139-154

References to SciGraph publications

  • 2003-08. A comparison of pebble tree transducers with macro tree transducers in ACTA INFORMATICA
  • 2002-09-02. Automata, Logic, and XML in COMPUTER SCIENCE LOGIC
  • 1971-06. Semantics of context-free languages: Correction in MATHEMATICAL SYSTEMS THEORY
  • 1998. Syntax-Directed Semantics, Formal Models Based on Tree Transducers in NONE
  • 2007. Complexity of Pebble Tree-Walking Automata in FUNDAMENTALS OF COMPUTATION THEORY
  • Journal

    TITLE

    Acta Informatica

    ISSUE

    2

    VOLUME

    46

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00236-008-0087-y

    DOI

    http://dx.doi.org/10.1007/s00236-008-0087-y

    DIMENSIONS

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


    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/0501", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Ecological Applications", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/05", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Environmental Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Leiden University", 
              "id": "https://www.grid.ac/institutes/grid.5132.5", 
              "name": [
                "LIACS, Leiden University, P.O. Box 9512, 2300 RA, Leiden, The Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Engelfriet", 
            "givenName": "Joost", 
            "id": "sg:person.014574236321.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-45793-3_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002630146", 
              "https://doi.org/10.1007/3-540-45793-3_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45793-3_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002630146", 
              "https://doi.org/10.1007/3-540-45793-3_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/322276.322283", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012725449"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1013725897", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-72248-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013725897", 
              "https://doi.org/10.1007/978-3-642-72248-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-72248-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013725897", 
              "https://doi.org/10.1007/978-3-642-72248-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00236-003-0120-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017699949", 
              "https://doi.org/10.1007/s00236-003-0120-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0019-9958(81)90466-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019022538"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/70642.70645", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020474542"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0019-9958(81)90438-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020821867"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0019-9958(83)80021-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024839424"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ipl.2003.05.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028702132"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74240-1_40", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029533294", 
              "https://doi.org/10.1007/978-3-540-74240-1_40"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74240-1_40", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029533294", 
              "https://doi.org/10.1007/978-3-540-74240-1_40"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1265530.1265540", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032487430"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1065167.1065203", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032583410"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/361227.361231", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032937511"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01702865", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041155488", 
              "https://doi.org/10.1007/bf01702865"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(85)90077-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044355124"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(85)90077-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044355124"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(02)00030-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052657880"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2009-04", 
        "datePublishedReg": "2009-04-01", 
        "description": "Tree-walking tree transducers can be typechecked in double exponential time. More generally, compositions of k tree-walking tree transducers can be typechecked in (k + 1)-fold exponential time. Consequently k-pebble tree transducers, which form a model of XML transformations and XML queries, can be typechecked in (k + 2)-fold exponential time. The results hold for both ranked and unranked trees.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00236-008-0087-y", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1133515", 
            "issn": [
              "0001-5903", 
              "1432-0525"
            ], 
            "name": "Acta Informatica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "46"
          }
        ], 
        "name": "The time complexity of typechecking tree-walking tree transducers", 
        "pagination": "139-154", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "0c95d2b21002d7819725db4f27f45cb0b915a0ef600d03450ef9cfd3a07b2520"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00236-008-0087-y"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1002643323"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00236-008-0087-y", 
          "https://app.dimensions.ai/details/publication/pub.1002643323"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T14:32", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000373_0000000373/records_13102_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00236-008-0087-y"
      }
    ]
     

    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/s00236-008-0087-y'

    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/s00236-008-0087-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00236-008-0087-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00236-008-0087-y'


     

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

    116 TRIPLES      21 PREDICATES      44 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00236-008-0087-y schema:about anzsrc-for:05
    2 anzsrc-for:0501
    3 schema:author Nf86dca4efd6e401ca9dea3b1b9f65f78
    4 schema:citation sg:pub.10.1007/3-540-45793-3_2
    5 sg:pub.10.1007/978-3-540-74240-1_40
    6 sg:pub.10.1007/978-3-642-72248-6
    7 sg:pub.10.1007/bf01702865
    8 sg:pub.10.1007/s00236-003-0120-0
    9 https://app.dimensions.ai/details/publication/pub.1013725897
    10 https://doi.org/10.1016/0304-3975(85)90077-5
    11 https://doi.org/10.1016/j.ipl.2003.05.001
    12 https://doi.org/10.1016/s0019-9958(81)90438-1
    13 https://doi.org/10.1016/s0019-9958(81)90466-6
    14 https://doi.org/10.1016/s0019-9958(83)80021-7
    15 https://doi.org/10.1016/s0022-0000(02)00030-2
    16 https://doi.org/10.1145/1065167.1065203
    17 https://doi.org/10.1145/1265530.1265540
    18 https://doi.org/10.1145/322276.322283
    19 https://doi.org/10.1145/361227.361231
    20 https://doi.org/10.1145/70642.70645
    21 schema:datePublished 2009-04
    22 schema:datePublishedReg 2009-04-01
    23 schema:description Tree-walking tree transducers can be typechecked in double exponential time. More generally, compositions of k tree-walking tree transducers can be typechecked in (k + 1)-fold exponential time. Consequently k-pebble tree transducers, which form a model of XML transformations and XML queries, can be typechecked in (k + 2)-fold exponential time. The results hold for both ranked and unranked trees.
    24 schema:genre research_article
    25 schema:inLanguage en
    26 schema:isAccessibleForFree false
    27 schema:isPartOf N3efd44ef00fd48d29b0f024f4db8a8f3
    28 Nc202fafa79fe4224b941d858d7d4f24a
    29 sg:journal.1133515
    30 schema:name The time complexity of typechecking tree-walking tree transducers
    31 schema:pagination 139-154
    32 schema:productId N20c7b71c0c734e89a32621ed85e08e77
    33 N349afbfcbee441ccb65bb1dbc01ab361
    34 Nee80b215d8834a70954b7608864f3421
    35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002643323
    36 https://doi.org/10.1007/s00236-008-0087-y
    37 schema:sdDatePublished 2019-04-11T14:32
    38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    39 schema:sdPublisher N494d20897f6743c4ba741c13e7251098
    40 schema:url http://link.springer.com/10.1007/s00236-008-0087-y
    41 sgo:license sg:explorer/license/
    42 sgo:sdDataset articles
    43 rdf:type schema:ScholarlyArticle
    44 N20c7b71c0c734e89a32621ed85e08e77 schema:name doi
    45 schema:value 10.1007/s00236-008-0087-y
    46 rdf:type schema:PropertyValue
    47 N349afbfcbee441ccb65bb1dbc01ab361 schema:name dimensions_id
    48 schema:value pub.1002643323
    49 rdf:type schema:PropertyValue
    50 N3efd44ef00fd48d29b0f024f4db8a8f3 schema:volumeNumber 46
    51 rdf:type schema:PublicationVolume
    52 N494d20897f6743c4ba741c13e7251098 schema:name Springer Nature - SN SciGraph project
    53 rdf:type schema:Organization
    54 Nc202fafa79fe4224b941d858d7d4f24a schema:issueNumber 2
    55 rdf:type schema:PublicationIssue
    56 Nee80b215d8834a70954b7608864f3421 schema:name readcube_id
    57 schema:value 0c95d2b21002d7819725db4f27f45cb0b915a0ef600d03450ef9cfd3a07b2520
    58 rdf:type schema:PropertyValue
    59 Nf86dca4efd6e401ca9dea3b1b9f65f78 rdf:first sg:person.014574236321.39
    60 rdf:rest rdf:nil
    61 anzsrc-for:05 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Environmental Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0501 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Ecological Applications
    66 rdf:type schema:DefinedTerm
    67 sg:journal.1133515 schema:issn 0001-5903
    68 1432-0525
    69 schema:name Acta Informatica
    70 rdf:type schema:Periodical
    71 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
    72 schema:familyName Engelfriet
    73 schema:givenName Joost
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
    75 rdf:type schema:Person
    76 sg:pub.10.1007/3-540-45793-3_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002630146
    77 https://doi.org/10.1007/3-540-45793-3_2
    78 rdf:type schema:CreativeWork
    79 sg:pub.10.1007/978-3-540-74240-1_40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029533294
    80 https://doi.org/10.1007/978-3-540-74240-1_40
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/978-3-642-72248-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013725897
    83 https://doi.org/10.1007/978-3-642-72248-6
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/bf01702865 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041155488
    86 https://doi.org/10.1007/bf01702865
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/s00236-003-0120-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017699949
    89 https://doi.org/10.1007/s00236-003-0120-0
    90 rdf:type schema:CreativeWork
    91 https://app.dimensions.ai/details/publication/pub.1013725897 schema:CreativeWork
    92 https://doi.org/10.1016/0304-3975(85)90077-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044355124
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1016/j.ipl.2003.05.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028702132
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1016/s0019-9958(81)90438-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020821867
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/s0019-9958(81)90466-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019022538
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/s0019-9958(83)80021-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024839424
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/s0022-0000(02)00030-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052657880
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1145/1065167.1065203 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032583410
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1145/1265530.1265540 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032487430
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1145/322276.322283 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012725449
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1145/361227.361231 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032937511
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1145/70642.70645 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020474542
    113 rdf:type schema:CreativeWork
    114 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
    115 schema:name LIACS, Leiden University, P.O. Box 9512, 2300 RA, Leiden, The Netherlands
    116 rdf:type schema:Organization
     




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


    ...