Context-free graph languages of bounded degree are generated by apex graph grammars |
| |
Authors: | Joost Engelfriet Linda Heyker George Leih |
| |
Affiliation: | (1) Department of Computer Science, Leiden University, P.O. Box 9512, NL-2300 RA Leiden, The Netherlands |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |