The complexity of graph languages generated by hyperedge replacement (Q2277851): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/bf00289017 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2088602194 / rank | |||
Normal rank | |||
Latest revision as of 11:11, 30 July 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The complexity of graph languages generated by hyperedge replacement |
scientific article |
Statements
The complexity of graph languages generated by hyperedge replacement (English)
0 references
1990
0 references
Hyperedge replacement grammars (HRGs) are a grammatical formalism for generating classes of graphs. The general parsing problem for HRGs is known to be NP-complete. The author analyses the difficulty of HRG parsing and develops certain conditions, on either the grammars or the input graphs, under which the parsing can be done either in polynomial time, or by efficient parallel algorithms.
0 references
graph grammars
0 references
hyperedge replacement
0 references
NP-complete
0 references
parsing
0 references
0 references
0 references
0 references
