Multiple Context-Free Tree Grammars and Multi-component Tree Adjoining Grammars View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2017-08-16

AUTHORS

Joost Engelfriet , Andreas Maletti

ABSTRACT

Strong lexicalization is the process of turning a grammar generating trees into an equivalent one, in which all rules contain a terminal leaf. It is known that tree adjoining grammars cannot be strongly lexicalized, whereas the more powerful simple context-free tree grammars can. It is demonstrated that multiple simple context-free tree grammars are as expressive as multi-component tree adjoining grammars and that both allow strong lexicalization. More... »

PAGES

217-229

References to SciGraph publications

  • 2010-04. Second-Order Abstract Categorial Grammars as Hyperedge Replacement Grammars in JOURNAL OF LOGIC, LANGUAGE AND INFORMATION
  • 2010. Dependency Structures and Lexicalized Grammars, An Algebraic Approach in NONE
  • 2011-07. The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-free Tree Grammars in JOURNAL OF LOGIC, LANGUAGE AND INFORMATION
  • 2000. Tree Languages Generated by Context-Free Graph Grammars in THEORY AND APPLICATION OF GRAPH TRANSFORMATIONS
  • 1997. Tree Languages in HANDBOOK OF FORMAL LANGUAGES
  • 2010. Parsing Beyond Context-Free Grammars in NONE
  • Book

    TITLE

    Fundamentals of Computation Theory

    ISBN

    978-3-662-55750-1
    978-3-662-55751-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-662-55751-8_18

    DOI

    http://dx.doi.org/10.1007/978-3-662-55751-8_18

    DIMENSIONS

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


    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/0607", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Plant Biology", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "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"
          }, 
          {
            "affiliation": {
              "name": [
                "Universit\u00e4t Leipzig, P.O. Box 100 920, 04009, 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/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-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/s10849-011-9134-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001865947", 
              "https://doi.org/10.1007/s10849-011-9134-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-46464-8_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005335661", 
              "https://doi.org/10.1007/978-3-540-46464-8_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(77)80034-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012047310"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14568-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013139874", 
              "https://doi.org/10.1007/978-3-642-14568-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14568-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013139874", 
              "https://doi.org/10.1007/978-3-642-14568-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14846-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019388454", 
              "https://doi.org/10.1007/978-3-642-14846-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14846-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019388454", 
              "https://doi.org/10.1007/978-3-642-14846-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10849-009-9109-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019879733", 
              "https://doi.org/10.1007/s10849-009-9109-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10849-009-9109-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019879733", 
              "https://doi.org/10.1007/s10849-009-9109-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(97)00190-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020637707"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1162/coli_a_00090", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031377591"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(75)80019-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035835232"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(91)90374-b", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036955638"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/800169.805428", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052858565"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.3115/981175.981190", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1099166582"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.3115/981175.981190", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1099166582"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2017-08-16", 
        "datePublishedReg": "2017-08-16", 
        "description": "Strong lexicalization is the process of turning a grammar generating trees into an equivalent one, in which all rules contain a terminal leaf. It is known that tree adjoining grammars cannot be strongly lexicalized, whereas the more powerful simple context-free tree grammars can. It is demonstrated that multiple simple context-free tree grammars are as expressive as multi-component tree adjoining grammars and that both allow strong lexicalization.", 
        "editor": [
          {
            "familyName": "Klasing", 
            "givenName": "Ralf", 
            "type": "Person"
          }, 
          {
            "familyName": "Zeitoun", 
            "givenName": "Marc", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-662-55751-8_18", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-662-55750-1", 
            "978-3-662-55751-8"
          ], 
          "name": "Fundamentals of Computation Theory", 
          "type": "Book"
        }, 
        "name": "Multiple Context-Free Tree Grammars and Multi-component Tree Adjoining Grammars", 
        "pagination": "217-229", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-662-55751-8_18"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "7401d3ea313b353cceddff4870c57582eca952a194eb8797763bd9bcfadf6ce7"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1091255618"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-662-55751-8_18", 
          "https://app.dimensions.ai/details/publication/pub.1091255618"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:00", 
        "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/0000000325_0000000325/records_100791_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-662-55751-8_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/978-3-662-55751-8_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/978-3-662-55751-8_18'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-55751-8_18'

    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-662-55751-8_18'


     

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

    124 TRIPLES      23 PREDICATES      39 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-662-55751-8_18 schema:about anzsrc-for:06
    2 anzsrc-for:0607
    3 schema:author N4f437d868e3e4e64b33db722075ab071
    4 schema:citation sg:pub.10.1007/978-3-540-46464-8_2
    5 sg:pub.10.1007/978-3-642-14568-1
    6 sg:pub.10.1007/978-3-642-14846-0
    7 sg:pub.10.1007/978-3-642-59126-6_1
    8 sg:pub.10.1007/s10849-009-9109-6
    9 sg:pub.10.1007/s10849-011-9134-0
    10 https://doi.org/10.1016/0304-3975(91)90374-b
    11 https://doi.org/10.1016/s0022-0000(75)80019-5
    12 https://doi.org/10.1016/s0022-0000(77)80034-2
    13 https://doi.org/10.1016/s0304-3975(97)00190-4
    14 https://doi.org/10.1145/800169.805428
    15 https://doi.org/10.1162/coli_a_00090
    16 https://doi.org/10.3115/981175.981190
    17 schema:datePublished 2017-08-16
    18 schema:datePublishedReg 2017-08-16
    19 schema:description Strong lexicalization is the process of turning a grammar generating trees into an equivalent one, in which all rules contain a terminal leaf. It is known that tree adjoining grammars cannot be strongly lexicalized, whereas the more powerful simple context-free tree grammars can. It is demonstrated that multiple simple context-free tree grammars are as expressive as multi-component tree adjoining grammars and that both allow strong lexicalization.
    20 schema:editor N6c696c6dcd7c4354a3a1aaa096dafdbc
    21 schema:genre chapter
    22 schema:inLanguage en
    23 schema:isAccessibleForFree false
    24 schema:isPartOf Ned35c06e594a4ba69dd75205e1adc2ee
    25 schema:name Multiple Context-Free Tree Grammars and Multi-component Tree Adjoining Grammars
    26 schema:pagination 217-229
    27 schema:productId N42de343e239b4211a598ff2e1ac26fac
    28 N815a8ea86a8c4f0a8db1ae53c52c40b9
    29 Na1145f89b5d64512970d4b7336c04ecf
    30 schema:publisher Ne1b5543f50e4432c9643b09d772c483d
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091255618
    32 https://doi.org/10.1007/978-3-662-55751-8_18
    33 schema:sdDatePublished 2019-04-16T05:00
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher N7ffcac0744cc4f798ebe7687ca993b42
    36 schema:url https://link.springer.com/10.1007%2F978-3-662-55751-8_18
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset chapters
    39 rdf:type schema:Chapter
    40 N1e8a8bb1b7ba4d0a990d09e8dbb2e916 schema:familyName Klasing
    41 schema:givenName Ralf
    42 rdf:type schema:Person
    43 N3dc92a16ea7c424dbd165da2e64b6681 rdf:first N9a1888f8af374fa59f0029abf5c9cef9
    44 rdf:rest rdf:nil
    45 N42de343e239b4211a598ff2e1ac26fac schema:name readcube_id
    46 schema:value 7401d3ea313b353cceddff4870c57582eca952a194eb8797763bd9bcfadf6ce7
    47 rdf:type schema:PropertyValue
    48 N4f437d868e3e4e64b33db722075ab071 rdf:first sg:person.014574236321.39
    49 rdf:rest N6f218bf0a6994093b0be2bf914f6758d
    50 N6c696c6dcd7c4354a3a1aaa096dafdbc rdf:first N1e8a8bb1b7ba4d0a990d09e8dbb2e916
    51 rdf:rest N3dc92a16ea7c424dbd165da2e64b6681
    52 N6f218bf0a6994093b0be2bf914f6758d rdf:first sg:person.016645332751.01
    53 rdf:rest rdf:nil
    54 N7ffcac0744cc4f798ebe7687ca993b42 schema:name Springer Nature - SN SciGraph project
    55 rdf:type schema:Organization
    56 N815a8ea86a8c4f0a8db1ae53c52c40b9 schema:name dimensions_id
    57 schema:value pub.1091255618
    58 rdf:type schema:PropertyValue
    59 N9a1888f8af374fa59f0029abf5c9cef9 schema:familyName Zeitoun
    60 schema:givenName Marc
    61 rdf:type schema:Person
    62 N9f8d264923794273b0c677f56c729a4d schema:name Universität Leipzig, P.O. Box 100 920, 04009, Leipzig, Germany
    63 rdf:type schema:Organization
    64 Na1145f89b5d64512970d4b7336c04ecf schema:name doi
    65 schema:value 10.1007/978-3-662-55751-8_18
    66 rdf:type schema:PropertyValue
    67 Ne1b5543f50e4432c9643b09d772c483d schema:location Berlin, Heidelberg
    68 schema:name Springer Berlin Heidelberg
    69 rdf:type schema:Organisation
    70 Ned35c06e594a4ba69dd75205e1adc2ee schema:isbn 978-3-662-55750-1
    71 978-3-662-55751-8
    72 schema:name Fundamentals of Computation Theory
    73 rdf:type schema:Book
    74 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Biological Sciences
    76 rdf:type schema:DefinedTerm
    77 anzsrc-for:0607 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Plant Biology
    79 rdf:type schema:DefinedTerm
    80 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
    81 schema:familyName Engelfriet
    82 schema:givenName Joost
    83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
    84 rdf:type schema:Person
    85 sg:person.016645332751.01 schema:affiliation N9f8d264923794273b0c677f56c729a4d
    86 schema:familyName Maletti
    87 schema:givenName Andreas
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
    89 rdf:type schema:Person
    90 sg:pub.10.1007/978-3-540-46464-8_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005335661
    91 https://doi.org/10.1007/978-3-540-46464-8_2
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/978-3-642-14568-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013139874
    94 https://doi.org/10.1007/978-3-642-14568-1
    95 rdf:type schema:CreativeWork
    96 sg:pub.10.1007/978-3-642-14846-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019388454
    97 https://doi.org/10.1007/978-3-642-14846-0
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1007/978-3-642-59126-6_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000867424
    100 https://doi.org/10.1007/978-3-642-59126-6_1
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/s10849-009-9109-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019879733
    103 https://doi.org/10.1007/s10849-009-9109-6
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/s10849-011-9134-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001865947
    106 https://doi.org/10.1007/s10849-011-9134-0
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1016/0304-3975(91)90374-b schema:sameAs https://app.dimensions.ai/details/publication/pub.1036955638
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1016/s0022-0000(75)80019-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035835232
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1016/s0022-0000(77)80034-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012047310
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1016/s0304-3975(97)00190-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020637707
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1145/800169.805428 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052858565
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1162/coli_a_00090 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031377591
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.3115/981175.981190 schema:sameAs https://app.dimensions.ai/details/publication/pub.1099166582
    121 rdf:type schema:CreativeWork
    122 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
    123 schema:name LIACS, Leiden University, P.O. Box 9512, 2300 RA, Leiden, The Netherlands
    124 rdf:type schema:Organization
     




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


    ...