The complexity of graph languages generated by hyperedge replacement (Q2277851): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
| Property / author | |||
| Property / author: Clemens Lautemann / rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Giora Slutzki / rank | |||
Revision as of 03:16, 11 February 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
