Branching Grammars: A Generalization of ET0L Systems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2003-06-18

AUTHORS

Frank Drewes , Joost Engelfriet

ABSTRACT

Generalizing ET0L systems, we introduce branching synchronization grammars with nested tables. Branching synchronization grammars with tables of nesting depth n have the same string- and tree-generating power as n-fold compositions of top-down tree transducers.

PAGES

266-278

References to SciGraph publications

  • 1973-12. Extension of tabled 0L-systems and languages in INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING
  • 1970-09. Mappings and grammars on trees in MATHEMATICAL SYSTEMS THEORY
  • 1981-12. Three hierarchies of transducers in MATHEMATICAL SYSTEMS THEORY
  • Book

    TITLE

    Developments in Language Theory

    ISBN

    978-3-540-40434-7
    978-3-540-45007-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-45007-6_21

    DOI

    http://dx.doi.org/10.1007/3-540-45007-6_21

    DIMENSIONS

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


    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", 
        "author": [
          {
            "affiliation": {
              "alternateName": "Ume\u00e5 University", 
              "id": "https://www.grid.ac/institutes/grid.12650.30", 
              "name": [
                "Department of Computing Science, Ume\u00e5 University, S-901 87, Ume\u00e5, Sweden"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Drewes", 
            "givenName": "Frank", 
            "id": "sg:person.015126303515.60", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015126303515.60"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Leiden University", 
              "id": "https://www.grid.ac/institutes/grid.5132.5", 
              "name": [
                "Department of Computer Science, Leiden University, P.O. Box 9612, NL-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": "https://doi.org/10.1016/s0019-9958(78)90538-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000196503"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(76)90003-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000617678"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(00)00168-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000771333"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(00)00280-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006939081"
            ], 
            "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/bf01786975", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018926352", 
              "https://doi.org/10.1007/bf01786975"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00985664", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021075152", 
              "https://doi.org/10.1007/bf00985664"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(70)80017-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022950527"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-0000(80)90058-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028307536"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "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/bf01695769", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033919759", 
              "https://doi.org/10.1007/bf01695769"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01695769", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033919759", 
              "https://doi.org/10.1007/bf01695769"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0205022", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841308"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2003-06-18", 
        "datePublishedReg": "2003-06-18", 
        "description": "Generalizing ET0L systems, we introduce branching synchronization grammars with nested tables. Branching synchronization grammars with tables of nesting depth n have the same string- and tree-generating power as n-fold compositions of top-down tree transducers.", 
        "editor": [
          {
            "familyName": "\u00c9sik", 
            "givenName": "Zolt\u00e1n", 
            "type": "Person"
          }, 
          {
            "familyName": "F\u00fcl\u00f6p", 
            "givenName": "Zolt\u00e1n", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-45007-6_21", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-40434-7", 
            "978-3-540-45007-8"
          ], 
          "name": "Developments in Language Theory", 
          "type": "Book"
        }, 
        "name": "Branching Grammars: A Generalization of ET0L Systems", 
        "pagination": "266-278", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-45007-6_21"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "21990beed3adc5ad8536cd931a4887b6e61b30cafe493c77ce6fbf8deb0ea145"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1007053179"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-45007-6_21", 
          "https://app.dimensions.ai/details/publication/pub.1007053179"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:28", 
        "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/0000000345_0000000345/records_64119_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-45007-6_21"
      }
    ]
     

    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/3-540-45007-6_21'

    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/3-540-45007-6_21'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45007-6_21'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-45007-6_21'


     

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

    105 TRIPLES      22 PREDICATES      34 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-45007-6_21 schema:author N3b9fbe1bf7014288ba83766404b9468e
    2 schema:citation sg:pub.10.1007/bf00985664
    3 sg:pub.10.1007/bf01695769
    4 sg:pub.10.1007/bf01786975
    5 https://doi.org/10.1016/0022-0000(80)90058-6
    6 https://doi.org/10.1016/0304-3975(76)90003-7
    7 https://doi.org/10.1016/s0019-9958(78)90538-7
    8 https://doi.org/10.1016/s0022-0000(70)80017-4
    9 https://doi.org/10.1016/s0304-3975(00)00168-7
    10 https://doi.org/10.1016/s0304-3975(00)00280-2
    11 https://doi.org/10.1137/0205022
    12 schema:datePublished 2003-06-18
    13 schema:datePublishedReg 2003-06-18
    14 schema:description Generalizing ET0L systems, we introduce branching synchronization grammars with nested tables. Branching synchronization grammars with tables of nesting depth n have the same string- and tree-generating power as n-fold compositions of top-down tree transducers.
    15 schema:editor N11176132baaa4dafb28a5497a67542dc
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree true
    19 schema:isPartOf Nf188db9d6f0b4707b975a463ef875399
    20 schema:name Branching Grammars: A Generalization of ET0L Systems
    21 schema:pagination 266-278
    22 schema:productId N1ca7331fe4b8466599699b7055196eab
    23 N261d0a1526ec48fbba1dceb8cc715bbc
    24 Ndbe563ccc5e9423fa9a051667bdbc0ca
    25 schema:publisher N132051ca3bd5446fa0c810ae18aeeb6b
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007053179
    27 https://doi.org/10.1007/3-540-45007-6_21
    28 schema:sdDatePublished 2019-04-16T05:28
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher Nbe21590f51ec4e6b9137fbffc32690a9
    31 schema:url https://link.springer.com/10.1007%2F3-540-45007-6_21
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset chapters
    34 rdf:type schema:Chapter
    35 N095603d7ea0b4c39bd577cba3e096bd0 rdf:first N7b5f75e9f8504a96a6e42fc973b7850c
    36 rdf:rest rdf:nil
    37 N11176132baaa4dafb28a5497a67542dc rdf:first Ne6515f15299c41bb823f06ccae061492
    38 rdf:rest N095603d7ea0b4c39bd577cba3e096bd0
    39 N132051ca3bd5446fa0c810ae18aeeb6b schema:location Berlin, Heidelberg
    40 schema:name Springer Berlin Heidelberg
    41 rdf:type schema:Organisation
    42 N1ca7331fe4b8466599699b7055196eab schema:name doi
    43 schema:value 10.1007/3-540-45007-6_21
    44 rdf:type schema:PropertyValue
    45 N261d0a1526ec48fbba1dceb8cc715bbc schema:name readcube_id
    46 schema:value 21990beed3adc5ad8536cd931a4887b6e61b30cafe493c77ce6fbf8deb0ea145
    47 rdf:type schema:PropertyValue
    48 N3b9fbe1bf7014288ba83766404b9468e rdf:first sg:person.015126303515.60
    49 rdf:rest Nfa560ad981d14d06b9b54fe303c77355
    50 N7b5f75e9f8504a96a6e42fc973b7850c schema:familyName Fülöp
    51 schema:givenName Zoltán
    52 rdf:type schema:Person
    53 Nbe21590f51ec4e6b9137fbffc32690a9 schema:name Springer Nature - SN SciGraph project
    54 rdf:type schema:Organization
    55 Ndbe563ccc5e9423fa9a051667bdbc0ca schema:name dimensions_id
    56 schema:value pub.1007053179
    57 rdf:type schema:PropertyValue
    58 Ne6515f15299c41bb823f06ccae061492 schema:familyName Ésik
    59 schema:givenName Zoltán
    60 rdf:type schema:Person
    61 Nf188db9d6f0b4707b975a463ef875399 schema:isbn 978-3-540-40434-7
    62 978-3-540-45007-8
    63 schema:name Developments in Language Theory
    64 rdf:type schema:Book
    65 Nfa560ad981d14d06b9b54fe303c77355 rdf:first sg:person.014574236321.39
    66 rdf:rest rdf:nil
    67 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
    68 schema:familyName Engelfriet
    69 schema:givenName Joost
    70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
    71 rdf:type schema:Person
    72 sg:person.015126303515.60 schema:affiliation https://www.grid.ac/institutes/grid.12650.30
    73 schema:familyName Drewes
    74 schema:givenName Frank
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015126303515.60
    76 rdf:type schema:Person
    77 sg:pub.10.1007/bf00985664 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021075152
    78 https://doi.org/10.1007/bf00985664
    79 rdf:type schema:CreativeWork
    80 sg:pub.10.1007/bf01695769 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033919759
    81 https://doi.org/10.1007/bf01695769
    82 rdf:type schema:CreativeWork
    83 sg:pub.10.1007/bf01786975 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018926352
    84 https://doi.org/10.1007/bf01786975
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/0022-0000(80)90058-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028307536
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1016/0304-3975(76)90003-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000617678
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1016/s0019-9958(78)90538-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000196503
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1016/s0022-0000(70)80017-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022950527
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1016/s0304-3975(00)00168-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000771333
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1016/s0304-3975(00)00280-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006939081
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1137/0205022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841308
    99 rdf:type schema:CreativeWork
    100 https://www.grid.ac/institutes/grid.12650.30 schema:alternateName Umeå University
    101 schema:name Department of Computing Science, Umeå University, S-901 87, Umeå, Sweden
    102 rdf:type schema:Organization
    103 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
    104 schema:name Department of Computer Science, Leiden University, P.O. Box 9612, NL-2300 RA, Leiden, The Netherlands
    105 rdf:type schema:Organization
     




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


    ...