A Greibach normal form for context-free graph grammars View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1992

AUTHORS

Joost Engelfriet

ABSTRACT

Every context-free hypergraph grammar that generates a language of bounded degree can be transformed into an equivalent one that has the apex property, i.e., that cannot “pass” nodes from nonterminal to nonterminal. This generalizes Double Greibach Normal Form of context-free grammars. Moreover, it provides a natural grammatical characterization of the context-free hypergraph languages of bounded degree. For grammars with the apex property it is not possible to put a bound on the number of nonterminals in the right-hand sides of the productions. More... »

PAGES

138-149

References to SciGraph publications

  • 1987-12. Graph expressions and graph rewritings in MATHEMATICAL SYSTEMS THEORY
  • Book

    TITLE

    Automata, Languages and Programming

    ISBN

    978-3-540-55719-7
    978-3-540-47278-0

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-55719-9_70

    DOI

    http://dx.doi.org/10.1007/3-540-55719-9_70

    DIMENSIONS

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


    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/2004", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Linguistics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/20", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Language, Communication and Culture", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Leiden University", 
              "id": "https://www.grid.ac/institutes/grid.5132.5", 
              "name": [
                "Department of Computer Science, Leiden University, P.O.Box 9512, 2300\u00a0RA 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.1145/321250.321254", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001877493"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01692060", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013326091", 
              "https://doi.org/10.1007/bf01692060"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01692060", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013326091", 
              "https://doi.org/10.1007/bf01692060"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01692060", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013326091", 
              "https://doi.org/10.1007/bf01692060"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(91)90174-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015370594"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0890-5401(90)90027-f", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026414335"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0890-5401(90)90043-h", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027180474"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0890-5401(90)90038-j", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033751887"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(87)90102-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038921884"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321406.321412", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047267403"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0890-5401(89)90030-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049234436"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1992", 
        "datePublishedReg": "1992-01-01", 
        "description": "Every context-free hypergraph grammar that generates a language of bounded degree can be transformed into an equivalent one that has the apex property, i.e., that cannot \u201cpass\u201d nodes from nonterminal to nonterminal. This generalizes Double Greibach Normal Form of context-free grammars. Moreover, it provides a natural grammatical characterization of the context-free hypergraph languages of bounded degree. For grammars with the apex property it is not possible to put a bound on the number of nonterminals in the right-hand sides of the productions.", 
        "editor": [
          {
            "familyName": "Kuich", 
            "givenName": "W.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-55719-9_70", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-55719-7", 
            "978-3-540-47278-0"
          ], 
          "name": "Automata, Languages and Programming", 
          "type": "Book"
        }, 
        "name": "A Greibach normal form for context-free graph grammars", 
        "pagination": "138-149", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-55719-9_70"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "08fb59a8cec2e2377f3a835f48220b778f3596015501c02e1e59f3789e069fe0"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1001885471"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-55719-9_70", 
          "https://app.dimensions.ai/details/publication/pub.1001885471"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T16:14", 
        "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_8675_00000244.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-55719-9_70"
      }
    ]
     

    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-55719-9_70'

    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-55719-9_70'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-55719-9_70'

    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-55719-9_70'


     

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

    93 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-55719-9_70 schema:about anzsrc-for:20
    2 anzsrc-for:2004
    3 schema:author Nc3eefacc5e15451cab53e9e52b9fbafc
    4 schema:citation sg:pub.10.1007/bf01692060
    5 https://doi.org/10.1016/0304-3975(87)90102-2
    6 https://doi.org/10.1016/0304-3975(91)90174-z
    7 https://doi.org/10.1016/0890-5401(89)90030-8
    8 https://doi.org/10.1016/0890-5401(90)90027-f
    9 https://doi.org/10.1016/0890-5401(90)90038-j
    10 https://doi.org/10.1016/0890-5401(90)90043-h
    11 https://doi.org/10.1145/321250.321254
    12 https://doi.org/10.1145/321406.321412
    13 schema:datePublished 1992
    14 schema:datePublishedReg 1992-01-01
    15 schema:description Every context-free hypergraph grammar that generates a language of bounded degree can be transformed into an equivalent one that has the apex property, i.e., that cannot “pass” nodes from nonterminal to nonterminal. This generalizes Double Greibach Normal Form of context-free grammars. Moreover, it provides a natural grammatical characterization of the context-free hypergraph languages of bounded degree. For grammars with the apex property it is not possible to put a bound on the number of nonterminals in the right-hand sides of the productions.
    16 schema:editor N74887a31cf1c451ca77f46c883445454
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree false
    20 schema:isPartOf Nf21780b0491748f18532a53b6252d8d6
    21 schema:name A Greibach normal form for context-free graph grammars
    22 schema:pagination 138-149
    23 schema:productId N0c11b0d2f6814f79943e53796972327c
    24 N8ca52306beab43cdb54520e0431a07b7
    25 Nb80234414dbb4f2183e81984085c0454
    26 schema:publisher Nf55823529615407c90f4675166b6e17e
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001885471
    28 https://doi.org/10.1007/3-540-55719-9_70
    29 schema:sdDatePublished 2019-04-15T16:14
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N8866e02e9292469c83a8206c1d7d0469
    32 schema:url http://link.springer.com/10.1007/3-540-55719-9_70
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N09a8bfa2400c4a39a4d4e615171c652c schema:familyName Kuich
    37 schema:givenName W.
    38 rdf:type schema:Person
    39 N0c11b0d2f6814f79943e53796972327c schema:name dimensions_id
    40 schema:value pub.1001885471
    41 rdf:type schema:PropertyValue
    42 N74887a31cf1c451ca77f46c883445454 rdf:first N09a8bfa2400c4a39a4d4e615171c652c
    43 rdf:rest rdf:nil
    44 N8866e02e9292469c83a8206c1d7d0469 schema:name Springer Nature - SN SciGraph project
    45 rdf:type schema:Organization
    46 N8ca52306beab43cdb54520e0431a07b7 schema:name doi
    47 schema:value 10.1007/3-540-55719-9_70
    48 rdf:type schema:PropertyValue
    49 Nb80234414dbb4f2183e81984085c0454 schema:name readcube_id
    50 schema:value 08fb59a8cec2e2377f3a835f48220b778f3596015501c02e1e59f3789e069fe0
    51 rdf:type schema:PropertyValue
    52 Nc3eefacc5e15451cab53e9e52b9fbafc rdf:first sg:person.014574236321.39
    53 rdf:rest rdf:nil
    54 Nf21780b0491748f18532a53b6252d8d6 schema:isbn 978-3-540-47278-0
    55 978-3-540-55719-7
    56 schema:name Automata, Languages and Programming
    57 rdf:type schema:Book
    58 Nf55823529615407c90f4675166b6e17e schema:location Berlin, Heidelberg
    59 schema:name Springer Berlin Heidelberg
    60 rdf:type schema:Organisation
    61 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Language, Communication and Culture
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Linguistics
    66 rdf:type schema:DefinedTerm
    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:pub.10.1007/bf01692060 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013326091
    73 https://doi.org/10.1007/bf01692060
    74 rdf:type schema:CreativeWork
    75 https://doi.org/10.1016/0304-3975(87)90102-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038921884
    76 rdf:type schema:CreativeWork
    77 https://doi.org/10.1016/0304-3975(91)90174-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1015370594
    78 rdf:type schema:CreativeWork
    79 https://doi.org/10.1016/0890-5401(89)90030-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049234436
    80 rdf:type schema:CreativeWork
    81 https://doi.org/10.1016/0890-5401(90)90027-f schema:sameAs https://app.dimensions.ai/details/publication/pub.1026414335
    82 rdf:type schema:CreativeWork
    83 https://doi.org/10.1016/0890-5401(90)90038-j schema:sameAs https://app.dimensions.ai/details/publication/pub.1033751887
    84 rdf:type schema:CreativeWork
    85 https://doi.org/10.1016/0890-5401(90)90043-h schema:sameAs https://app.dimensions.ai/details/publication/pub.1027180474
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.1145/321250.321254 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001877493
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1145/321406.321412 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047267403
    90 rdf:type schema:CreativeWork
    91 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
    92 schema:name Department of Computer Science, Leiden University, P.O.Box 9512, 2300 RA Leiden, The Netherlands
    93 rdf:type schema:Organization
     




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


    ...