The complexity of graph languages generated by hyperedge replacement (Q2277851): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 06:33, 5 March 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
