Context-free graph languages of bounded degree are generated by apex graph grammars (Q1338891)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Context-free graph languages of bounded degree are generated by apex graph grammars |
scientific article; zbMATH DE number 694999
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Context-free graph languages of bounded degree are generated by apex graph grammars |
scientific article; zbMATH DE number 694999 |
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
0 references
0 references
