Graph Grammars with Negative Application Conditions
Graph Grammars with Negative Application Conditions
复制标题
具有否定应用条件的图文法
DOI：
--
复制
发表时间：
1996
影响因子：
0.8
通讯作者：
G. Taentzer
中科院分区：
文献类型：
--
作者：
A. Habel;R. Heckel;G. Taentzer
在每一个图形语法方法，它是定义如何以及在何种条件下，图生产可以应用于一个给定的图，以获得一个派生的图。可以应用产生式的条件称为应用条件。虽然大多数已知的通用图语法方法的生成能力足以生成任何递归可重复的图集，但对于每个产生式具有特定的应用条件通常是方便的。这样的应用条件，一方面，包括上下文条件，如节点、边或给定图中的某些子图的存在或不存在，以及关于从产生式的左手侧到给定图的态射的嵌入限制。本文将Ehrig和Habel提出的应用条件的概念限定为语境条件，特别是否定条件。除了一般的概念，我们国家的局部合流和应用条件的导子定理。最后，我们研究了上下文无关文法的应用条件，就其生成能力。
In each graph-grammar approach it is defined how and under which conditions graph productions can be applied to a given graph in order to obtain a derived graph. The conditions under which productions can be applied are called application conditions. Although the generative power of most of the known general graph-grammar approaches is sufficient to generate any recursively enumerable set of graphs, it is often convenient to have specific application conditions for each production. Such application conditions, on the one hand, include context conditions like the existence or non-existence of nodes, edges, or certain subgraphs in the given graph as well as embedding restrictions concerning the morphisms from the left-hand side of the production to the given graph. In this paper, the concept of application conditions introduced by Ehrig and Habel is restricted to contextual conditions, especially negative ones. In addition to the general concept, we state local confluence and the Parallelism Theorem for derivations with application conditions. Finally we study context-free graph grammars with application conditions with respect to their generative power.