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 N972e6a99a66640cb937e370e7dc09e4e
    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 N7f79a2a69e8b40ab8a5c83195abf5ab4
    21 schema:genre chapter
    22 schema:inLanguage en
    23 schema:isAccessibleForFree false
    24 schema:isPartOf N722f3e00f0f64b5283cda9a4d3760850
    25 schema:name Multiple Context-Free Tree Grammars and Multi-component Tree Adjoining Grammars
    26 schema:pagination 217-229
    27 schema:productId N3e106e62e8d3489999baa52db8c9d440
    28 Nc8eddf0740174185956451c2e5e3cfb0
    29 Nfb2a7d7b81de446b85a34d79062b3736
    30 schema:publisher N48b5b8bf9e7a4653a3ef501d334ce1bd
    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 Nd821175f3bf1498c93eb62e5e6c81b5b
    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 N3e106e62e8d3489999baa52db8c9d440 schema:name dimensions_id
    41 schema:value pub.1091255618
    42 rdf:type schema:PropertyValue
    43 N48b5b8bf9e7a4653a3ef501d334ce1bd schema:location Berlin, Heidelberg
    44 schema:name Springer Berlin Heidelberg
    45 rdf:type schema:Organisation
    46 N722f3e00f0f64b5283cda9a4d3760850 schema:isbn 978-3-662-55750-1
    47 978-3-662-55751-8
    48 schema:name Fundamentals of Computation Theory
    49 rdf:type schema:Book
    50 N7f79a2a69e8b40ab8a5c83195abf5ab4 rdf:first Nbc89d104b948435e9dafd9681a153b1a
    51 rdf:rest N86e764d5b503449eb165554a758f2cfb
    52 N86e764d5b503449eb165554a758f2cfb rdf:first Na962add1b78b406f9cd3c97b2774de6a
    53 rdf:rest rdf:nil
    54 N972e6a99a66640cb937e370e7dc09e4e rdf:first sg:person.014574236321.39
    55 rdf:rest Na73c432fb415488d940e3ceed7ea6a65
    56 Na73c432fb415488d940e3ceed7ea6a65 rdf:first sg:person.016645332751.01
    57 rdf:rest rdf:nil
    58 Na962add1b78b406f9cd3c97b2774de6a schema:familyName Zeitoun
    59 schema:givenName Marc
    60 rdf:type schema:Person
    61 Nbc89d104b948435e9dafd9681a153b1a schema:familyName Klasing
    62 schema:givenName Ralf
    63 rdf:type schema:Person
    64 Nc8eddf0740174185956451c2e5e3cfb0 schema:name readcube_id
    65 schema:value 7401d3ea313b353cceddff4870c57582eca952a194eb8797763bd9bcfadf6ce7
    66 rdf:type schema:PropertyValue
    67 Nd821175f3bf1498c93eb62e5e6c81b5b schema:name Springer Nature - SN SciGraph project
    68 rdf:type schema:Organization
    69 Need2d7a44f224b6788e6abfe64ab6e21 schema:name Universität Leipzig, P.O. Box 100 920, 04009, Leipzig, Germany
    70 rdf:type schema:Organization
    71 Nfb2a7d7b81de446b85a34d79062b3736 schema:name doi
    72 schema:value 10.1007/978-3-662-55751-8_18
    73 rdf:type schema:PropertyValue
    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 Need2d7a44f224b6788e6abfe64ab6e21
    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)


    ...