Nonterminal separation in graph grammars (Q804300)

The eNLCE model of graph grammars was introduced as a variation of the successful NLC model. In a NLC grammar the left hand side of a production is a single labeled node, the right hand side is a node labeled graph and the embedding mechanism depends solely on the labels of the nodes involved. In the case of eNCE grammars the embedding mechanism makes use of the identity (rather than the label) of the nodes in the right-hand side of the productions, the generated graphs have also edge labels, the embedding mechanism also uses the labels of the edges incident with the replaced node. In a previous paper the authors have shown that eNCE grammars are more powerful than NLC grammars. It also shown that boundary eNCE grammars (such that there are no edges between nonterminal nodes in any sentential form or, in other words, such that the distance between nonterminals is at least two) are confluent (namely, if two nodes in a graph can be replaced they can be replaced in any order). The present paper investigates the general notion of distance between nonterminal nodes in eNCE grammars. An eNCE grammar is called k- separated, for \(k\geq 1\), if the distance between any two nonterminal nodes in its sentential forms is \(\geq k\). Having previously shown that 1- separated grammars are more powerful than 2-separated grammars, the authors prove that 2-separated grammars are more powerful than 3- separated grammars and conjecture that, for \(k\geq 3\), k-separated grammars are more powerful than \((k+1)\)-separated grammars. Another considered restriction on graph grammars is an apex restriction. An eNCE grammar is an apex eNCE grammar if the embedding mechanism can only establish edges between terminal nodes. For apex grammars to be k- separated has no influence on the generating power, namely it is shown that each apex language can be generated by a k-separated apex grammar.