NONTERMINAL SEPARATION IN GRAPH-GRAMMARS

被引：13
|
作者：
ENGELFRIET, J
LEIH, G
ROZENBERG, G
机构：
[1] Department of Computer Science, Leiden University, 2300 RA Leiden
来源：
THEORETICAL COMPUTER SCIENCE | 1991年 / 82卷 / 01期
关键词：
D O I：
10.1016/0304-3975(91)90174-Z
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The notion of nonterminal separation in eNCE graph grammars is introduced: such a graph grammar is k-separated (with k greater-than-or-equal-to 1) if the distance between any two nonterminal nodes in any of its sentential forms is at least k (2-separated eNCE grammars are known as boundary eNCE graph grammars). There exists a 2-separated eNCE graph language that is not 3-separated. Apex eNCE graph grammars can be arbitrarily separated: every apex eNCE graph language can be generated by a k-separated apex eNCE grammar, for every k.
引用
收藏
页码：95 / 111
页数：17
相关论文
共 50 条
12345