Composition Closure of Linear Extended Top-down Tree Transducers View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2015-12-29

AUTHORS

Joost Engelfriet, Zoltán Fülöp, Andreas Maletti

ABSTRACT

Linear extended top-down tree transducers (or synchronous tree-substitution grammars) are popular formal models of tree transformations that are extensively used in syntax-based statistical machine translation. The expressive power of compositions of such transducers with and without regular look-ahead is investigated. In particular, the restrictions of ε-freeness, strictness, and nondeletion are considered. The composition hierarchy turns out to be finite for all ε-free (all rules consume input) variants of these transducers except for the nondeleting ε-free transducers. The least number of transducers needed for the full expressive power of arbitrary compositions is presented. In all remaining cases (incl. the nondeleting ε-free transducers) the composition hierarchy does not collapse. More... »

PAGES

129-171

References to SciGraph publications

  • 1975-06. Bottom-up and top-down tree transformations— a comparison in THEORY OF COMPUTING SYSTEMS
  • 1976-12. Top-down tree transducers with regular look-ahead in THEORY OF COMPUTING SYSTEMS
  • 1970-09. Mappings and grammars on trees in THEORY OF COMPUTING SYSTEMS
  • 1998. Syntax-Directed Semantics, Formal Models Based on Tree Transducers in NONE
  • 1997. Tree Languages in HANDBOOK OF FORMAL LANGUAGES
  • 2005. An Overview of Probabilistic Tree Transducers for Natural Language Processing in COMPUTATIONAL LINGUISTICS AND INTELLIGENT TEXT PROCESSING
  • 1981-12. Three hierarchies of transducers in THEORY OF COMPUTING SYSTEMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-015-9660-2

    DOI

    http://dx.doi.org/10.1007/s00224-015-9660-2

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Statistics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Leiden Institute of Advanced Computer Science, Leiden University, P.O. Box 9512, 2300 RA, Leiden, The Netherlands", 
              "id": "http://www.grid.ac/institutes/grid.5132.5", 
              "name": [
                "Leiden Institute of Advanced Computer Science, 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"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Foundations of Computer Science, University of Szeged, \u00c1rp\u00e1d t\u00e9r 2, H-6720, Szeged, Hungary", 
              "id": "http://www.grid.ac/institutes/grid.9008.1", 
              "name": [
                "Department of Foundations of Computer Science, University of Szeged, \u00c1rp\u00e1d t\u00e9r 2, H-6720, Szeged, Hungary"
              ], 
              "type": "Organization"
            }, 
            "familyName": "F\u00fcl\u00f6p", 
            "givenName": "Zolt\u00e1n", 
            "id": "sg:person.014007607055.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institute of Computer Science, Universit\u00e4t Leipzig, Augustusplatz 10\u201311, 04109, Leipzig, Germany", 
              "id": "http://www.grid.ac/institutes/None", 
              "name": [
                "Institute of Computer Science, Universit\u00e4t Leipzig, Augustusplatz 10\u201311, 04109, Leipzig, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Maletti", 
            "givenName": "Andreas", 
            "id": "sg:person.016645332751.01", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01695769", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033919759", 
              "https://doi.org/10.1007/bf01695769"
            ], 
            "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/bf01704020", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006876172", 
              "https://doi.org/10.1007/bf01704020"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-59126-6_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000867424", 
              "https://doi.org/10.1007/978-3-642-59126-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/bf01786975", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018926352", 
              "https://doi.org/10.1007/bf01786975"
            ], 
            "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"
          }
        ], 
        "datePublished": "2015-12-29", 
        "datePublishedReg": "2015-12-29", 
        "description": "Linear extended top-down tree transducers (or synchronous tree-substitution grammars) are popular formal models of tree transformations that are extensively used in syntax-based statistical machine translation. The expressive power of compositions of such transducers with and without regular look-ahead is investigated. In particular, the restrictions of \u03b5-freeness, strictness, and nondeletion are considered. The composition hierarchy turns out to be finite for all \u03b5-free (all rules consume input) variants of these transducers except for the nondeleting \u03b5-free transducers. The least number of transducers needed for the full expressive power of arbitrary compositions is presented. In all remaining cases (incl. the nondeleting \u03b5-free transducers) the composition hierarchy does not collapse.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-015-9660-2", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.4191088", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "60"
          }
        ], 
        "keywords": [
          "syntax-based statistical machine translation", 
          "linear", 
          "tree transducers", 
          "popular formal model", 
          "formal model", 
          "model", 
          "tree transformations", 
          "transformation", 
          "statistical machine translation", 
          "machine translation", 
          "translation", 
          "expressive power", 
          "power", 
          "such transducers", 
          "restriction", 
          "freeness", 
          "strictness", 
          "composition hierarchy", 
          "hierarchy", 
          "free variant", 
          "variants", 
          "least number", 
          "number", 
          "full expressive power", 
          "arbitrary composition", 
          "cases", 
          "closure", 
          "top", 
          "transducer", 
          "composition", 
          "nondeletion", 
          "free transducers", 
          "composition closure", 
          "Linear Extended Top", 
          "Extended Top"
        ], 
        "name": "Composition Closure of Linear Extended Top-down Tree Transducers", 
        "pagination": "129-171", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1037877916"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-015-9660-2"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-015-9660-2", 
          "https://app.dimensions.ai/details/publication/pub.1037877916"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-11-01T18:23", 
        "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/article/article_651.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-015-9660-2"
      }
    ]
     

    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/s00224-015-9660-2'

    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/s00224-015-9660-2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-015-9660-2'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-015-9660-2'


     

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

    143 TRIPLES      22 PREDICATES      67 URIs      52 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-015-9660-2 schema:about anzsrc-for:01
    2 anzsrc-for:0104
    3 schema:author Nc31dadf5679f45f1bfd446be3e9c0407
    4 schema:citation sg:pub.10.1007/978-3-540-30586-6_1
    5 sg:pub.10.1007/978-3-642-59126-6_1
    6 sg:pub.10.1007/978-3-642-72248-6
    7 sg:pub.10.1007/bf01683280
    8 sg:pub.10.1007/bf01695769
    9 sg:pub.10.1007/bf01704020
    10 sg:pub.10.1007/bf01786975
    11 schema:datePublished 2015-12-29
    12 schema:datePublishedReg 2015-12-29
    13 schema:description Linear extended top-down tree transducers (or synchronous tree-substitution grammars) are popular formal models of tree transformations that are extensively used in syntax-based statistical machine translation. The expressive power of compositions of such transducers with and without regular look-ahead is investigated. In particular, the restrictions of ε-freeness, strictness, and nondeletion are considered. The composition hierarchy turns out to be finite for all ε-free (all rules consume input) variants of these transducers except for the nondeleting ε-free transducers. The least number of transducers needed for the full expressive power of arbitrary compositions is presented. In all remaining cases (incl. the nondeleting ε-free transducers) the composition hierarchy does not collapse.
    14 schema:genre article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree true
    17 schema:isPartOf N7e52aaaac2d44f478757a0503d2b1d83
    18 Na4fc25e3c32041928d38081081376142
    19 sg:journal.1052098
    20 schema:keywords Extended Top
    21 Linear Extended Top
    22 arbitrary composition
    23 cases
    24 closure
    25 composition
    26 composition closure
    27 composition hierarchy
    28 expressive power
    29 formal model
    30 free transducers
    31 free variant
    32 freeness
    33 full expressive power
    34 hierarchy
    35 least number
    36 linear
    37 machine translation
    38 model
    39 nondeletion
    40 number
    41 popular formal model
    42 power
    43 restriction
    44 statistical machine translation
    45 strictness
    46 such transducers
    47 syntax-based statistical machine translation
    48 top
    49 transducer
    50 transformation
    51 translation
    52 tree transducers
    53 tree transformations
    54 variants
    55 schema:name Composition Closure of Linear Extended Top-down Tree Transducers
    56 schema:pagination 129-171
    57 schema:productId N02456c24eb1c4ae68708659ff8803947
    58 N902ec82159974d0ca74077ac41836d08
    59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037877916
    60 https://doi.org/10.1007/s00224-015-9660-2
    61 schema:sdDatePublished 2021-11-01T18:23
    62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    63 schema:sdPublisher N68d4ec52916740fab643443b582bab66
    64 schema:url https://doi.org/10.1007/s00224-015-9660-2
    65 sgo:license sg:explorer/license/
    66 sgo:sdDataset articles
    67 rdf:type schema:ScholarlyArticle
    68 N02456c24eb1c4ae68708659ff8803947 schema:name dimensions_id
    69 schema:value pub.1037877916
    70 rdf:type schema:PropertyValue
    71 N68d4ec52916740fab643443b582bab66 schema:name Springer Nature - SN SciGraph project
    72 rdf:type schema:Organization
    73 N6b70619035c8409585105219cc9aa626 rdf:first sg:person.014007607055.43
    74 rdf:rest Nad2c1bf6d4b04149b1611a13435f1f43
    75 N7e52aaaac2d44f478757a0503d2b1d83 schema:volumeNumber 60
    76 rdf:type schema:PublicationVolume
    77 N902ec82159974d0ca74077ac41836d08 schema:name doi
    78 schema:value 10.1007/s00224-015-9660-2
    79 rdf:type schema:PropertyValue
    80 Na4fc25e3c32041928d38081081376142 schema:issueNumber 2
    81 rdf:type schema:PublicationIssue
    82 Nad2c1bf6d4b04149b1611a13435f1f43 rdf:first sg:person.016645332751.01
    83 rdf:rest rdf:nil
    84 Nc31dadf5679f45f1bfd446be3e9c0407 rdf:first sg:person.014574236321.39
    85 rdf:rest N6b70619035c8409585105219cc9aa626
    86 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    87 schema:name Mathematical Sciences
    88 rdf:type schema:DefinedTerm
    89 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Statistics
    91 rdf:type schema:DefinedTerm
    92 sg:grant.4191088 http://pending.schema.org/fundedItem sg:pub.10.1007/s00224-015-9660-2
    93 rdf:type schema:MonetaryGrant
    94 sg:journal.1052098 schema:issn 1432-4350
    95 1433-0490
    96 schema:name Theory of Computing Systems
    97 schema:publisher Springer Nature
    98 rdf:type schema:Periodical
    99 sg:person.014007607055.43 schema:affiliation grid-institutes:grid.9008.1
    100 schema:familyName Fülöp
    101 schema:givenName Zoltán
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43
    103 rdf:type schema:Person
    104 sg:person.014574236321.39 schema:affiliation grid-institutes:grid.5132.5
    105 schema:familyName Engelfriet
    106 schema:givenName Joost
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
    108 rdf:type schema:Person
    109 sg:person.016645332751.01 schema:affiliation grid-institutes:None
    110 schema:familyName Maletti
    111 schema:givenName Andreas
    112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
    113 rdf:type schema:Person
    114 sg:pub.10.1007/978-3-540-30586-6_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002480445
    115 https://doi.org/10.1007/978-3-540-30586-6_1
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/978-3-642-59126-6_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000867424
    118 https://doi.org/10.1007/978-3-642-59126-6_1
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-642-72248-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013725897
    121 https://doi.org/10.1007/978-3-642-72248-6
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/bf01683280 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014989626
    124 https://doi.org/10.1007/bf01683280
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/bf01695769 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033919759
    127 https://doi.org/10.1007/bf01695769
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/bf01704020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006876172
    130 https://doi.org/10.1007/bf01704020
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/bf01786975 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018926352
    133 https://doi.org/10.1007/bf01786975
    134 rdf:type schema:CreativeWork
    135 grid-institutes:None schema:alternateName Institute of Computer Science, Universität Leipzig, Augustusplatz 10–11, 04109, Leipzig, Germany
    136 schema:name Institute of Computer Science, Universität Leipzig, Augustusplatz 10–11, 04109, Leipzig, Germany
    137 rdf:type schema:Organization
    138 grid-institutes:grid.5132.5 schema:alternateName Leiden Institute of Advanced Computer Science, Leiden University, P.O. Box 9512, 2300 RA, Leiden, The Netherlands
    139 schema:name Leiden Institute of Advanced Computer Science, Leiden University, P.O. Box 9512, 2300 RA, Leiden, The Netherlands
    140 rdf:type schema:Organization
    141 grid-institutes:grid.9008.1 schema:alternateName Department of Foundations of Computer Science, University of Szeged, Árpád tér 2, H-6720, Szeged, Hungary
    142 schema:name Department of Foundations of Computer Science, University of Szeged, Árpád tér 2, H-6720, Szeged, Hungary
    143 rdf:type schema:Organization
     




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


    ...