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 N859d68d77ead4f04b04f6c637798a608
    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 Ne061b34a545445f6a4a89537a2f72a19
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree false
    20 schema:isPartOf N95e00f889dcf418fa2a9f8c10bc0eb08
    21 schema:name A Greibach normal form for context-free graph grammars
    22 schema:pagination 138-149
    23 schema:productId N8ebc10e7dada432aa94b7dee0e7eeb97
    24 Naabe2e2c1a06418b9dab8abf55927f0e
    25 Naf8067a8ec7541528a61475806fd4f79
    26 schema:publisher N5f70cd42b94e4d05bbdfe7a85d8e228f
    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 N27727263fa5c4203ae761e0b91d95047
    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 N27727263fa5c4203ae761e0b91d95047 schema:name Springer Nature - SN SciGraph project
    37 rdf:type schema:Organization
    38 N5f70cd42b94e4d05bbdfe7a85d8e228f schema:location Berlin, Heidelberg
    39 schema:name Springer Berlin Heidelberg
    40 rdf:type schema:Organisation
    41 N859d68d77ead4f04b04f6c637798a608 rdf:first sg:person.014574236321.39
    42 rdf:rest rdf:nil
    43 N8ebc10e7dada432aa94b7dee0e7eeb97 schema:name readcube_id
    44 schema:value 08fb59a8cec2e2377f3a835f48220b778f3596015501c02e1e59f3789e069fe0
    45 rdf:type schema:PropertyValue
    46 N95e00f889dcf418fa2a9f8c10bc0eb08 schema:isbn 978-3-540-47278-0
    47 978-3-540-55719-7
    48 schema:name Automata, Languages and Programming
    49 rdf:type schema:Book
    50 Naabe2e2c1a06418b9dab8abf55927f0e schema:name doi
    51 schema:value 10.1007/3-540-55719-9_70
    52 rdf:type schema:PropertyValue
    53 Naf8067a8ec7541528a61475806fd4f79 schema:name dimensions_id
    54 schema:value pub.1001885471
    55 rdf:type schema:PropertyValue
    56 Ne061b34a545445f6a4a89537a2f72a19 rdf:first Nfbeea3264d0f4a40afc396f18ac94911
    57 rdf:rest rdf:nil
    58 Nfbeea3264d0f4a40afc396f18ac94911 schema:familyName Kuich
    59 schema:givenName W.
    60 rdf:type schema:Person
    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)


    ...