Context-free graph languages of bounded degree are generated by apex graph grammars (Q1338891): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 14:30, 31 January 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Context-free graph languages of bounded degree are generated by apex graph grammars |
scientific article |
Statements
Context-free graph languages of bounded degree are generated by apex graph grammars (English)
0 references
23 November 1994
0 references
The apex graph grammars generate precisely the context-free graph languages of bounded degree, independently of whether one considers hyperedge replacement systems or (boundary or confluent) NLC or edNCE graph grammars. The main feature of apex graph grammars is that nodes cannot be ``passed'' from nonterminal to nonterminal. The proof is based on a normal form result for arbitrary hyperedge replacement systems that forbids ``passing chains''. This generalizes Greibach Normal Form.
0 references
apex graph grammars
0 references
context-free graph languages
0 references
