NCE graph grammar

NCE graph grammar --- графовая грамматика типа NCE.

An NCE graph grammar (or neighborhood controlled embedding graph grammar) is a system [math]\displaystyle{ {\mathcal G} = (\Sigma, \Delta, S, P) }[/math], where

(1) [math]\displaystyle{ \Delta }[/math] and [math]\displaystyle{ \Sigma }[/math] are alphabets with [math]\displaystyle{ \Delta \subseteq \Sigma }[/math] as the set of terminal node labels, and [math]\displaystyle{ \Sigma - \Delta }[/math] as the set of nonterminal node labels, respectively.

(2) [math]\displaystyle{ S }[/math] is a graph over [math]\displaystyle{ \Sigma }[/math], the axiom of [math]\displaystyle{ {\mathcal G} }[/math].

(3) [math]\displaystyle{ P }[/math] is a finite set of productions. Each production is a triple [math]\displaystyle{ (A,R,C) }[/math], where [math]\displaystyle{ A }[/math] is a nonterminal node label from [math]\displaystyle{ \Sigma - \Delta }[/math] (the left-hand side), [math]\displaystyle{ R }[/math] is a graph over [math]\displaystyle{ \Sigma }[/math] (the right-hand side), and [math]\displaystyle{ C }[/math] is an embedding relation for [math]\displaystyle{ R }[/math].

There are the following types of NCE graph grammars: confluent (C-NCE), boundary (B-NCE), and linear (L-NCE).