The complexity of graph languages generated by hyperedge replacement View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1990-04

AUTHORS

Clemens Lautemann

ABSTRACT

Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing. More... »

PAGES

399-421

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf00289017

DOI

http://dx.doi.org/10.1007/bf00289017

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Fachbereich Mathematik, Johannes Gutenberg-Universit\u00e4t, Saarstrasse 21, D-6500, Mainz, Federal Republic of Germany", 
          "id": "http://www.grid.ac/institutes/grid.5802.f", 
          "name": [
            "Fachbereich Mathematik, Johannes Gutenberg-Universit\u00e4t, Saarstrasse 21, D-6500, Mainz, Federal Republic of Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lautemann", 
        "givenName": "Clemens", 
        "id": "sg:person.01216265025.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01216265025.01"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-50939-9_138", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028665390", 
          "https://doi.org/10.1007/3-540-50939-9_138"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0039608", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024940782", 
          "https://doi.org/10.1007/bfb0039608"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00288976", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033100693", 
          "https://doi.org/10.1007/bf00288976"
        ], 
        "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/bfb0025713", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1108495084", 
          "https://doi.org/10.1007/bfb0025713"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-18771-5_62", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017932709", 
          "https://doi.org/10.1007/3-540-18771-5_62"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-19488-6_128", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043894630", 
          "https://doi.org/10.1007/3-540-19488-6_128"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00289155", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021576206", 
          "https://doi.org/10.1007/bf00289155"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0026094", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030671823", 
          "https://doi.org/10.1007/bfb0026094"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-18771-5_48", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046278326", 
          "https://doi.org/10.1007/3-540-18771-5_48"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1990-04", 
    "datePublishedReg": "1990-04-01", 
    "description": "Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf00289017", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1133515", 
        "issn": [
          "0001-5903", 
          "1432-0525"
        ], 
        "name": "Acta Informatica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "5", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "27"
      }
    ], 
    "keywords": [
      "log-space reducible", 
      "parsing problem", 
      "graph grammars", 
      "input graph", 
      "polynomial time", 
      "graph languages", 
      "Chomsky grammars", 
      "parsing", 
      "hyperedge replacement", 
      "string parsing", 
      "main difficulty", 
      "grammar", 
      "graph", 
      "complexity", 
      "language", 
      "NP", 
      "strings", 
      "generating mechanism", 
      "way", 
      "reducible", 
      "difficulties", 
      "time", 
      "realm", 
      "cases", 
      "mechanism", 
      "conditions", 
      "replacement", 
      "problem", 
      "paper", 
      "hyperedge replacement graph grammars", 
      "replacement graph grammars", 
      "graph generating mechanisms", 
      "context-free Chomsky grammars", 
      "realm of string", 
      "HRG parsing", 
      "context-free string parsing"
    ], 
    "name": "The complexity of graph languages generated by hyperedge replacement", 
    "pagination": "399-421", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027175395"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf00289017"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf00289017", 
      "https://app.dimensions.ai/details/publication/pub.1027175395"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-11-01T18:00", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_259.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf00289017"
  }
]
 

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/bf00289017'

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/bf00289017'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf00289017'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf00289017'


 

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

134 TRIPLES      22 PREDICATES      72 URIs      54 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf00289017 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ndfbde180e6ea41348e287a2836c2a098
4 schema:citation sg:pub.10.1007/3-540-18771-5_48
5 sg:pub.10.1007/3-540-18771-5_62
6 sg:pub.10.1007/3-540-19488-6_128
7 sg:pub.10.1007/3-540-50939-9_138
8 sg:pub.10.1007/bf00288976
9 sg:pub.10.1007/bf00289155
10 sg:pub.10.1007/bf01692060
11 sg:pub.10.1007/bfb0025713
12 sg:pub.10.1007/bfb0026094
13 sg:pub.10.1007/bfb0039608
14 schema:datePublished 1990-04
15 schema:datePublishedReg 1990-04-01
16 schema:description Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.
17 schema:genre article
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf N67a31d2fe3cf4245813b5a65a4ef81a8
21 Nc4e392466c2b49138aacb53b322c416c
22 sg:journal.1133515
23 schema:keywords Chomsky grammars
24 HRG parsing
25 NP
26 cases
27 complexity
28 conditions
29 context-free Chomsky grammars
30 context-free string parsing
31 difficulties
32 generating mechanism
33 grammar
34 graph
35 graph generating mechanisms
36 graph grammars
37 graph languages
38 hyperedge replacement
39 hyperedge replacement graph grammars
40 input graph
41 language
42 log-space reducible
43 main difficulty
44 mechanism
45 paper
46 parsing
47 parsing problem
48 polynomial time
49 problem
50 realm
51 realm of string
52 reducible
53 replacement
54 replacement graph grammars
55 string parsing
56 strings
57 time
58 way
59 schema:name The complexity of graph languages generated by hyperedge replacement
60 schema:pagination 399-421
61 schema:productId Nc532c2a6d9ae40fab0321763ebac3456
62 Ncdf838f8eecb44ceada201628ce872dc
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027175395
64 https://doi.org/10.1007/bf00289017
65 schema:sdDatePublished 2021-11-01T18:00
66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
67 schema:sdPublisher N6e04968210e24791821be1ae22c442a6
68 schema:url https://doi.org/10.1007/bf00289017
69 sgo:license sg:explorer/license/
70 sgo:sdDataset articles
71 rdf:type schema:ScholarlyArticle
72 N67a31d2fe3cf4245813b5a65a4ef81a8 schema:issueNumber 5
73 rdf:type schema:PublicationIssue
74 N6e04968210e24791821be1ae22c442a6 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 Nc4e392466c2b49138aacb53b322c416c schema:volumeNumber 27
77 rdf:type schema:PublicationVolume
78 Nc532c2a6d9ae40fab0321763ebac3456 schema:name dimensions_id
79 schema:value pub.1027175395
80 rdf:type schema:PropertyValue
81 Ncdf838f8eecb44ceada201628ce872dc schema:name doi
82 schema:value 10.1007/bf00289017
83 rdf:type schema:PropertyValue
84 Ndfbde180e6ea41348e287a2836c2a098 rdf:first sg:person.01216265025.01
85 rdf:rest rdf:nil
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
90 schema:name Computation Theory and Mathematics
91 rdf:type schema:DefinedTerm
92 sg:journal.1133515 schema:issn 0001-5903
93 1432-0525
94 schema:name Acta Informatica
95 schema:publisher Springer Nature
96 rdf:type schema:Periodical
97 sg:person.01216265025.01 schema:affiliation grid-institutes:grid.5802.f
98 schema:familyName Lautemann
99 schema:givenName Clemens
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01216265025.01
101 rdf:type schema:Person
102 sg:pub.10.1007/3-540-18771-5_48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046278326
103 https://doi.org/10.1007/3-540-18771-5_48
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/3-540-18771-5_62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017932709
106 https://doi.org/10.1007/3-540-18771-5_62
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/3-540-19488-6_128 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043894630
109 https://doi.org/10.1007/3-540-19488-6_128
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/3-540-50939-9_138 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028665390
112 https://doi.org/10.1007/3-540-50939-9_138
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/bf00288976 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033100693
115 https://doi.org/10.1007/bf00288976
116 rdf:type schema:CreativeWork
117 sg:pub.10.1007/bf00289155 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021576206
118 https://doi.org/10.1007/bf00289155
119 rdf:type schema:CreativeWork
120 sg:pub.10.1007/bf01692060 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013326091
121 https://doi.org/10.1007/bf01692060
122 rdf:type schema:CreativeWork
123 sg:pub.10.1007/bfb0025713 schema:sameAs https://app.dimensions.ai/details/publication/pub.1108495084
124 https://doi.org/10.1007/bfb0025713
125 rdf:type schema:CreativeWork
126 sg:pub.10.1007/bfb0026094 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030671823
127 https://doi.org/10.1007/bfb0026094
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/bfb0039608 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024940782
130 https://doi.org/10.1007/bfb0039608
131 rdf:type schema:CreativeWork
132 grid-institutes:grid.5802.f schema:alternateName Fachbereich Mathematik, Johannes Gutenberg-Universität, Saarstrasse 21, D-6500, Mainz, Federal Republic of Germany
133 schema:name Fachbereich Mathematik, Johannes Gutenberg-Universität, Saarstrasse 21, D-6500, Mainz, Federal Republic of Germany
134 rdf:type schema:Organization
 




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


...