How to Remove the Look-Ahead of Top-Down Tree Transducers View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Joost Engelfriet , Sebastian Maneth , Helmut Seidl

ABSTRACT

For a top-down tree transducer with regular look-ahead we introduce the notion of difference bound, which is a number bounding the difference in output height for any two look-ahead states of the transducer. We present an algorithm that, for a given transducer with a known difference bound, decides whether it is equivalent to a transducer without regular look-ahead, and constructs such a transducer if the answer is positive. All transducers are total and deterministic. More... »

PAGES

103-115

References to SciGraph publications

  • 2012. Visibly Pushdown Transducers with Look-Ahead in SOFSEM 2012: THEORY AND PRACTICE OF COMPUTER SCIENCE
  • 2005. An Overview of Probabilistic Tree Transducers for Natural Language Processing in COMPUTATIONAL LINGUISTICS AND INTELLIGENT TEXT PROCESSING
  • 1979. Transductions and Context-Free Languages in NONE
  • 1976-12. Top-down tree transducers with regular look-ahead in MATHEMATICAL SYSTEMS THEORY
  • 2012. Streaming Tree Transducers in AUTOMATA, LANGUAGES, AND PROGRAMMING
  • Book

    TITLE

    Developments in Language Theory

    ISBN

    978-3-319-09697-1
    978-3-319-09698-8

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-09698-8_10

    DOI

    http://dx.doi.org/10.1007/978-3-319-09698-8_10

    DIMENSIONS

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


    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/0303", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Macromolecular and Materials Chemistry", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/03", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Chemical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Leiden University", 
              "id": "https://www.grid.ac/institutes/grid.5132.5", 
              "name": [
                "LIACS, Leiden University, 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"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Edinburgh", 
              "id": "https://www.grid.ac/institutes/grid.4305.2", 
              "name": [
                "School of Informatics, University of Edinburgh, United Kingdom"
              ], 
              "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": "Technical University Munich", 
              "id": "https://www.grid.ac/institutes/grid.6936.a", 
              "name": [
                "Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, 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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-540-30586-6_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002480445", 
              "https://doi.org/10.1007/978-3-540-30586-6_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30586-6_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002480445", 
              "https://doi.org/10.1007/978-3-540-30586-6_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-663-09367-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003958860", 
              "https://doi.org/10.1007/978-3-663-09367-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-663-09367-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003958860", 
              "https://doi.org/10.1007/978-3-663-09367-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(77)90049-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007813537"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-0000(85)90066-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012161455"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01683280", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014989626", 
              "https://doi.org/10.1007/bf01683280"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01683280", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014989626", 
              "https://doi.org/10.1007/bf01683280"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ic.2008.01.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016848252"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-31585-5_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017902924", 
              "https://doi.org/10.1007/978-3-642-31585-5_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-27660-6_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037455666", 
              "https://doi.org/10.1007/978-3-642-27660-6_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1807085.1807122", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039908256"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jcss.2009.01.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048971550"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/070699160", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062851455"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511762093", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098700870"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2014", 
        "datePublishedReg": "2014-01-01", 
        "description": "For a top-down tree transducer with regular look-ahead we introduce the notion of difference bound, which is a number bounding the difference in output height for any two look-ahead states of the transducer. We present an algorithm that, for a given transducer with a known difference bound, decides whether it is equivalent to a transducer without regular look-ahead, and constructs such a transducer if the answer is positive. All transducers are total and deterministic.", 
        "editor": [
          {
            "familyName": "Shur", 
            "givenName": "Arseny M.", 
            "type": "Person"
          }, 
          {
            "familyName": "Volkov", 
            "givenName": "Mikhail V.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-09698-8_10", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-319-09697-1", 
            "978-3-319-09698-8"
          ], 
          "name": "Developments in Language Theory", 
          "type": "Book"
        }, 
        "name": "How to Remove the Look-Ahead of Top-Down Tree Transducers", 
        "pagination": "103-115", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-09698-8_10"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "4d75170c70d28654867cfeb76fcb5aa1c17ec27245786c12ef97e85761c3680e"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1016256298"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-09698-8_10", 
          "https://app.dimensions.ai/details/publication/pub.1016256298"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T14:23", 
        "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/0000000001_0000000264/records_8669_00000253.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-319-09698-8_10"
      }
    ]
     

    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/978-3-319-09698-8_10'

    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/978-3-319-09698-8_10'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-09698-8_10'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-09698-8_10'


     

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

    131 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-09698-8_10 schema:about anzsrc-for:03
    2 anzsrc-for:0303
    3 schema:author N1b1c3ed7203e459ea192abdd435ce232
    4 schema:citation sg:pub.10.1007/978-3-540-30586-6_1
    5 sg:pub.10.1007/978-3-642-27660-6_21
    6 sg:pub.10.1007/978-3-642-31585-5_8
    7 sg:pub.10.1007/978-3-663-09367-1
    8 sg:pub.10.1007/bf01683280
    9 https://doi.org/10.1016/0022-0000(85)90066-2
    10 https://doi.org/10.1016/0304-3975(77)90049-4
    11 https://doi.org/10.1016/j.ic.2008.01.002
    12 https://doi.org/10.1016/j.jcss.2009.01.001
    13 https://doi.org/10.1017/cbo9780511762093
    14 https://doi.org/10.1137/070699160
    15 https://doi.org/10.1145/1807085.1807122
    16 schema:datePublished 2014
    17 schema:datePublishedReg 2014-01-01
    18 schema:description For a top-down tree transducer with regular look-ahead we introduce the notion of difference bound, which is a number bounding the difference in output height for any two look-ahead states of the transducer. We present an algorithm that, for a given transducer with a known difference bound, decides whether it is equivalent to a transducer without regular look-ahead, and constructs such a transducer if the answer is positive. All transducers are total and deterministic.
    19 schema:editor N240a149cf6d84301a8cd085a3c91af3d
    20 schema:genre chapter
    21 schema:inLanguage en
    22 schema:isAccessibleForFree true
    23 schema:isPartOf N5765fcffa1b94cd2821f5e5f57737ff8
    24 schema:name How to Remove the Look-Ahead of Top-Down Tree Transducers
    25 schema:pagination 103-115
    26 schema:productId N1b28a8f29e504f1b8b44563d28900b56
    27 N6189027034ec40b4936468dbd2ec5361
    28 N82c1596262ce40b7850b66d040bc20f9
    29 schema:publisher Nb39aa97a0ac94e849314b94a0609891e
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016256298
    31 https://doi.org/10.1007/978-3-319-09698-8_10
    32 schema:sdDatePublished 2019-04-15T14:23
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N55714c10186f4c2baf74f3ae2c30a81a
    35 schema:url http://link.springer.com/10.1007/978-3-319-09698-8_10
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset chapters
    38 rdf:type schema:Chapter
    39 N1b1c3ed7203e459ea192abdd435ce232 rdf:first sg:person.014574236321.39
    40 rdf:rest Nc01b614adc9a4465a2eb536d8d8aac8c
    41 N1b28a8f29e504f1b8b44563d28900b56 schema:name doi
    42 schema:value 10.1007/978-3-319-09698-8_10
    43 rdf:type schema:PropertyValue
    44 N240a149cf6d84301a8cd085a3c91af3d rdf:first N795aed42cc9341d1a5c37a1c24eff167
    45 rdf:rest N4e8c90eebe0d4f71b728df5490d3d307
    46 N4e8c90eebe0d4f71b728df5490d3d307 rdf:first Ndffb09ce100e4390a2ae37ba9a266ca1
    47 rdf:rest rdf:nil
    48 N55714c10186f4c2baf74f3ae2c30a81a schema:name Springer Nature - SN SciGraph project
    49 rdf:type schema:Organization
    50 N5765fcffa1b94cd2821f5e5f57737ff8 schema:isbn 978-3-319-09697-1
    51 978-3-319-09698-8
    52 schema:name Developments in Language Theory
    53 rdf:type schema:Book
    54 N6189027034ec40b4936468dbd2ec5361 schema:name dimensions_id
    55 schema:value pub.1016256298
    56 rdf:type schema:PropertyValue
    57 N795aed42cc9341d1a5c37a1c24eff167 schema:familyName Shur
    58 schema:givenName Arseny M.
    59 rdf:type schema:Person
    60 N82c1596262ce40b7850b66d040bc20f9 schema:name readcube_id
    61 schema:value 4d75170c70d28654867cfeb76fcb5aa1c17ec27245786c12ef97e85761c3680e
    62 rdf:type schema:PropertyValue
    63 N8ba43e897d7646539465c2e0628ecac8 rdf:first sg:person.0600150505.21
    64 rdf:rest rdf:nil
    65 Nb39aa97a0ac94e849314b94a0609891e schema:location Cham
    66 schema:name Springer International Publishing
    67 rdf:type schema:Organisation
    68 Nc01b614adc9a4465a2eb536d8d8aac8c rdf:first sg:person.016240662443.33
    69 rdf:rest N8ba43e897d7646539465c2e0628ecac8
    70 Ndffb09ce100e4390a2ae37ba9a266ca1 schema:familyName Volkov
    71 schema:givenName Mikhail V.
    72 rdf:type schema:Person
    73 anzsrc-for:03 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Chemical Sciences
    75 rdf:type schema:DefinedTerm
    76 anzsrc-for:0303 schema:inDefinedTermSet anzsrc-for:
    77 schema:name Macromolecular and Materials Chemistry
    78 rdf:type schema:DefinedTerm
    79 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
    80 schema:familyName Engelfriet
    81 schema:givenName Joost
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
    83 rdf:type schema:Person
    84 sg:person.016240662443.33 schema:affiliation https://www.grid.ac/institutes/grid.4305.2
    85 schema:familyName Maneth
    86 schema:givenName Sebastian
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
    88 rdf:type schema:Person
    89 sg:person.0600150505.21 schema:affiliation https://www.grid.ac/institutes/grid.6936.a
    90 schema:familyName Seidl
    91 schema:givenName Helmut
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0600150505.21
    93 rdf:type schema:Person
    94 sg:pub.10.1007/978-3-540-30586-6_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002480445
    95 https://doi.org/10.1007/978-3-540-30586-6_1
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/978-3-642-27660-6_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037455666
    98 https://doi.org/10.1007/978-3-642-27660-6_21
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/978-3-642-31585-5_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017902924
    101 https://doi.org/10.1007/978-3-642-31585-5_8
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/978-3-663-09367-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003958860
    104 https://doi.org/10.1007/978-3-663-09367-1
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/bf01683280 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014989626
    107 https://doi.org/10.1007/bf01683280
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1016/0022-0000(85)90066-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012161455
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1016/0304-3975(77)90049-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007813537
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1016/j.ic.2008.01.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016848252
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1016/j.jcss.2009.01.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048971550
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1017/cbo9780511762093 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098700870
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1137/070699160 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062851455
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1145/1807085.1807122 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039908256
    122 rdf:type schema:CreativeWork
    123 https://www.grid.ac/institutes/grid.4305.2 schema:alternateName University of Edinburgh
    124 schema:name School of Informatics, University of Edinburgh, United Kingdom
    125 rdf:type schema:Organization
    126 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
    127 schema:name LIACS, Leiden University, The Netherlands
    128 rdf:type schema:Organization
    129 https://www.grid.ac/institutes/grid.6936.a schema:alternateName Technical University Munich
    130 schema:name Institut für Informatik, Technische Universität München, Germany
    131 rdf:type schema:Organization
     




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


    ...