[3]Lisa Mathew

1]Department of Computer Science and Engineering, Amal Jyothi College of
Engineering, Kanjirappally, Kottayam, 686 518, Kerala, India

2]Research scholar, APJ Abdul Kalam Technological University, CET Campus,
Thiruvananthapuram, 695 016, Kerala, India

3]Department of Basic Sciences , Amal Jyothi College of Engineering,
Kanjirappally, Kottayam, 686 518, Kerala, India

# On Some Closure Properties of nc-eNCE Graph Grammars

Jayakrishna Vijayakumar<EMAIL_ADDRESS><EMAIL_ADDRESS>[  [  [

###### Abstract

In the study of automata and grammars, closure properties of the associated
languages have been studied extensively. In particular, closure properties of
various types of graph grammars have been examined in (Rozenberg and Welzl,
Inf. and Control,1986) and (Rozenberg and Welzl, Acta Informatica,1986). In
this paper we examine some critical closure properties of the nc-eNCE graph
grammars discussed in (Jayakrishna and Mathew, Symmetry 2023) and (Jayakrishna
and Mathew, ICMICDS 2022).

###### keywords:

Graph Grammars, Confluence, Connection Instructions, Regular Control, Jumping
Graph Grammars, Closure Properties, Disjoint Sum, Kleene Sum, Union, Star
Concatenation, Chain Concatenation

##  1 Introduction

Graph grammars have been a challenging area of research in theoretical
computer science since their introduction in the sixties [1, 2, 3, 4, 5, 6,
7]. They provide a framework for specifying the structure and transformation
of graphs and hence are capable of generating a wide range of graphs using a
small set of rules. Thus the creation of complex structures that would be
difficult to specify using other methods becomes possible. They are often used
in computer science to specify the structural and behavioral aspects of
software systems. For instance, they can be used to specify the structure of a
database schema [1], a programming language or a software architecture. They
also find application in other fields, such as biology, to model the structure
and behavior of biological systems. Moreover, they can be used to specify the
behavior of a system over time, thus facilitating the modeling of dynamic
systems.

Graph grammars consist primarily of a set of rules which specify how to
iteratively transform a graph by adding, deleting, or modifying its nodes and
edges- [7, 8]. A typical graph grammar consists of $(i)$ a start graph $S$ and
$(ii)$ a set $P$ of transformation rules (productions). These rules help to
convert the host graph $H$ (initially the host graph is $S$) to the desired
transformed graph. The rules have an crucial role in the transformation and
are of the form $P(M,D,E)$, where $M$ is the mother graph to be replaced
(present in $H$), $D$ (daughter graph) is the graph which replaces $M$ , and
$E$ is the embedding mechanism which describes how the daughter graph $D$ is
connected to the the remaining portion of the host graph $(H^{\prime}=H-M)$ .

On the other hand, a class of graph languages can have two types of operations
defined on it- set operations and operations on graphs belonging to the
language. Set operations include union, intersection and complementation while
operations on graphs include disjoint sum (graph theoretical union), graph
complementation and others including some new operations which we define here.
Closure properties of some special types types of graph grammars have been
examined in [9, 10] Here, we examine some salient closure properties of the
nc-eNCE graph grammars discussed in [11]and [12].

In Section 2 we recall some preliminary notions about nc-eNCE. Section 3 of
this paper introduces a variety of operations on Graph Languages and a few
other related concepts. In Section 4 we prove that these languages are closed
under the operations of union, disjoint sum and Kleene sum. Closure properties
under two more operations - Chain concatenation and star concatenation are
also discussed. Since the proofs of the closure properties with respect to
these two operations employ jumping connection instructions the class of
jumping nc-eNCE graph grammars are closed under these operations. We conclude
our discussion in Section 5

##  2 Preliminaries

Gluing and connecting are the two popular mechanisms used to embed the
daughter graph in the mother graph.In the gluing approach [1, 2, 3, 5],
certain nodes and edges of $H^{\prime}$ and of $D$ are identified for fusion.
The edges thus identified are those which were originally incident to $M$ in
$H$. There are different ways of identifying the corresponding nodes in the
host and daughter graphs. One way is to use labels or attributes attached to
the nodes/edges. Another way is to use a mapping function that associates each
node/edge in the daughter graph with a node in the host graph.

Hierarchical gluing is a technique that allows us to glue multiple graphs in a
hierarchical manner. In this approach, we first glue two or more graphs to
form a larger graph and then repeat the process with the remaining graphs
until the desired graph is obtained. The gluing approach is commonly used in
graph compression and graph visualization, where it can simplify the display
of complex graphs by representing subgraphs with a single node.

The connecting approach is another way of embedding daughter graphs in the
host graph. In this approach, the daughter graph is connected to the host
graph by adding edges between designated nodes in the two graphs. The edges
represent the relationships between the nodes in the daughter graph and the
nodes in the host graph.

The connecting approach is suitable when the embedded graph is small compared
to the host graph. In this case, it may not be necessary to replace nodes in
the host graph with the daughter graph. Instead, the relationships between the
nodes in the daughter graph and the nodes in the host graph can be represented
using edges. This is known as edge replacement. The connecting approach is
usually used in graph query processing, where it is used to match smaller
graphs against a larger graph. It may also be used in graph editing tools,
where it can be used to insert and delete subgraphs within a larger graph.

The gluing approach is advantageous when the embedded graph needs to be
modified frequently or when the embedded graph is large compared to the host
graph. The gluing approach is generally more expensive than the connecting
approach in terms of computational complexity, since it requires the
replacement of nodes in the host graph with the daughter graph. The connecting
approach, on the other hand, only requires the addition of edges between the
daughter graph and the host graph.

###  2.1 Graph Grammars with Regular Control

Graph grammars with regular control are a variant of graph grammars that use
regular expressions to specify the control flow of the transformation rules.
Regular expressions are used to specify the conditions under which a
production rule can be applied. The evolution of graphs are determined by the
regular expression which controls the order of application of rules. Such
graph grammars are known as non-confluent graph grammars. One such variant of
this type specified in [11] is Non-confluent Edge and Node Controlled
Embedding $(nc-eNCE)$ Graph Grammar.

Non-confluent Edge and Node Controlled Embedding $(nc-eNCE)$ Graph Grammar
[11]: Restricting the sequence of production rules utilized results in this
type of graph grammar that introduces a small amount of determinism to the
essentially non-deterministic concept of a graph grammar.

######  Definition 1.

[13, 11] A construct $ncG=$( $\Sigma,\Delta,\Gamma,\Omega,P,G_{S},R(P)$) is
known as an $nc-eNCE$ graph grammar where

  * $\Sigma$ and $\Gamma$ are sets of symbols used to label nodes and edges respectively,

  * $\Delta$ and $\Omega$ are the collections of terminal symbols in $\Sigma$ and $\Gamma$ respectively,

  * A production rule in $P$, $p:A\rightarrow(D,C)$ acting on the mother node $M$ with label $A$ has a collection C of connection instructions $(a,p\mid q,B)$ associated with it. Here $x$ with label $a$ is a neighbor of $M$ and $B$ is a node in $D$. The edge $p$ which connected $x$ and $M$ is removed and a new edge $q$ is established between $x$ and $B$.

  * $G_{S}$ is the initial graph,

  * The regular control, $R(P)$, regulates the sequence of application of the production rules.

Several variants of $nc-eNCE$ graph grammars such as nc-$eNCE$ graph grammar
with deletion $(dnc-eNCE)$, nc-$eNCE$ graph grammar with $\psi$ labelled edges
$(\psi nc-eNCE)$, etc have been discussed in [11].

###  2.2 Jumping Graph Grammar

A jumping graph grammar ($JGG$) differs from its conventional
counterpart(jumping gramars) [14, 15] in the fact that in addition to the
normal connections established as part of daughter graph embedding with
vertices which were adjacent to the vertices of the mother graph, we can also
create extra edges known as jumping edges to establish connections from
vertices of daughter graph to other vertices in the rest of the host graph.
The formal definition of jumping graph grammars is as follows.

######  Definition 2.

[12] A Jumping Graph Grammar is a construct $JGG=$($\Sigma,P,C,S$), where

  * $\Sigma$ is the finite set of node labels

  * $P$ is the finite set of graph production rules

  * $C$ is the connection instruction

  * $G_{S}$ is the start/initial graph

Here $P$ is of the form $P:M\rightarrow D$ where $M$ is the mother graph to be
replaced by daughter graph $D$.

In general graph grammars, the connection instruction $C$ establishes edges
from the designated nodes of $D$ to the nodes of $M$ which were having
incident edges to the mother graph that were removed during replacement. But
in jumping graph grammars, the connection instruction has an extended
capability to establish edges from designated nodes of $D$ to any of the nodes
present in $G_{S}\backslash M$.
The language represented by the jumping graph grammar $JGG$ is
$L$($JGG$)$~{}={\\{G|G_{S}\overset{*}{\implies}G\\}}$ where, $G$ is the set of
graphs obtained from $G_{S}$ by recursively applying rules in $P$.

###  2.3 Non-confluent Edge and Node Controlled Embedding Jumping Graph
grammars (nc-eNCE-JGG)

We extend the definition of $nc-eNCE$ graph grammar in [13] for defining this
new grammar. Formally, we have:

######  Definition 3.

An $nc-eNCE-JGG$ graph grammar is a 7 tuple:
$ncJGG=\text{(}\Sigma,\Delta,\Gamma,\Omega,$ $P,G_{S},R\text{(}P\text{)}$)
where

  * $\Sigma$ is the set of node labels,

  * $\Delta$ is the set of terminal node labels,

  * $\Gamma$ is the set of edge labels,

  * $\Omega$ is the set of terminal edge labels,

  * The productions in $P$ are of one of the forms $p:A\rightarrow\text{(}D,C$) where $A$ is the label of the mother node and $D$ is the daughter graph. The connection instruction $C$ can be in any one of the following forms

    1. 1.

($a,p\mid q,B$), where $p$ and $q$ are edge labels, $a$ is the node label of
one of the neighbours of the mother node and $B$ is a node in $D$. The
interpretation is that we find an edge labelled $p$ in the host graph which
had connected a node $x$ labelled $a$ to the mother node and create a new edge
labelled $q$ between $x$ and the node $B$ in the daughter graph

    2. 2.

($a,\alpha,b$), where $a$ is the node label of one of the nodes in $D$, $b$ is
the label of any of the nodes in remaining graph after removing the mother
node and $\alpha$ is the label of the new edge connecting $a$ and $b$.

  * $G_{S}$ is the start/initial graph,

  * $R\text{(}P$) is a regular control which specifies the order of application of the productions, Hence this grammar becomes restricted or non-confluent.

The language represented by this grammar is $L\text{(}ncJGG\text{)}={\\{G\in
G_{\Delta}|G_{S}\overset{R\text{(}P\text{)}}{\implies}G\\}}$ where
$G_{\Delta}$ is the set of graphs containing only terminal nodes. Hence the
language of an $nc-eNCE-JGG$ graph grammar is a set of graphs whose nodes have
terminal labels, generated by applying a series of productions in the order
$p_{1},p_{2},\cdots,p_{n}$ where $p_{1}p_{2}\cdots p_{n}$ is a word in the
language represented by the regular control $R\text{(}P$).

##  3 Operations on Graph Languages

######  Definition 4.

The union of two graph languages $L_{1}$ and $L_{2}$ is the graph language
obtained by taking the usual union of the two families of graphs i.e.
$L=L_{1}\cup L_{2}$

######  Definition 5.

The disjoint sum of two graph languages $L_{1}$ and $L_{2}$ is the graph
language$L_{1}\oplus L_{2}$ obtained by taking the disjoint sum of sample
graphs from two languages i.e. $L_{1}\oplus L_{2}=\\{G_{1}+G_{2}|G_{1}\in
L_{1},G_{2}\in L_{2}\\}$.

######  Definition 6.

The Kleene sum of a graph language $L$ is the graph language obtained by
taking the disjoint sum of a countable number of sample graphs from $L$ i.e.
$L^{\oplus}=\\{G_{1}+G_{2}+\cdots G_{n}|G_{i}\in L,1\leq i\leq n\\}$

######  Definition 7.

Let $L$ be a graph language generated by a graph grammar $G$, the set of
graphs obtained by ignoring the labels of graphs in $L$ forms the underlying
graph language $U(L)$.

######  Definition 8.

The chain concatenation of two graph languages $L_{1}$ and $L_{2}$ which do
not contain null graphs is the graph language obtained by joining the two
designated nodes chosen from sample graphs $G_{1}$ and $G_{2}$ in $L_{1}$ and
$L_{2}$ respectively and is denoted by$L_{1}\odot L_{2}$

######  Definition 9.

The star concatenation of a graph language $L_{1}$ is the graph language
obtained by connecting designated nodes in a countable number of sample graphs
from $L_{1}$ to a central node. This is denoted by $L_{1}^{\circledast}$.

##  4 Closure Properties of Graph Languages Generated Using nc-eNCE Graph
Grammar

The class of graph languages generated using $nc-eNCE$ Graph Grammar is closed
under union, disjoint sum, Kleene sum and chain concatenation.

######  THeorem 1.

The class of string languages generated using nc-eNCE graph grammars is closed
under the operation union.

###### Proof.

Consider two $nc-eNCE$ graph grammars
$ncG_{1}=(\Sigma_{1},\Delta_{1},\Gamma_{1},\Omega_{1},P_{1},S_{1},$
$R_{1}(P_{1}))$ and
$ncG_{2}=(\Sigma_{2},\Delta_{2},\Gamma_{2},\Omega_{2},P_{2},S_{2},R_{2}(P_{2}))$
generating graph languages $L_{1}$ and $L_{2}$ respectively. Assuming that $S$
is a new symbol that does not appear in $\Sigma_{1}\cup\Sigma_{2}$, we define
a new $nc-eNCE$ graph grammar $ncG$ capable of generating the language
$L=L_{1}UL_{2}$ as follows.

$ncG=(\Sigma,\Delta,\Gamma,\Omega,P,S,R(P))~{}~{}\text{where}$

,

  * $\Sigma=\Sigma_{1}\cup\Sigma_{2}\cup\\{S\\}$

  * $\Delta=\Delta_{1}\cup\Delta_{2}$

  * $\Gamma=\Gamma_{1}\cup\Gamma_{2}$

  * $\Omega=\Omega_{1}\cup\Omega_{2}$

  * $P=P_{1}\cup P_{2}\cup\\{p_{01},p_{02}\\}$

  * R(P)= $[p_{01}.R_{1}(P_{1})]+[p_{02}.R_{2}(P_{2})]$

$p_{01}$$S$$~{}\rightarrow$$S_{1}$$C_{01}=\phi$$p_{02}:$$S$$~{}\rightarrow$$S_{2}$$C_{02}=\phi$
Figure 1: New Production for generation of union of graph languages

Here $S_{1}$ and $S_{2}$ are the start graphs of $ncG_{1}$ and $ncG_{2}$
respectively. Clearly any graph in $L_{1}$ can be generated using
$[p_{01}.R_{1}(P_{1})]$ while any graph in $L_{2}$ can be generated using
$[p_{02}.R_{2}(P_{2})]$. ∎

######  THeorem 2.

The class of graph languages generated using $nc-eNCE$ graph grammars is
closed under the graph operation disjoint sum.

###### Proof.

Consider two $nc-eNCE$ graph grammars
$ncG_{1}=(\Sigma_{1},\Delta_{1},\Gamma_{1},\Omega_{1},P_{1},S_{1},$
$R_{1}(P_{1}))$ and
$ncG_{2}=(\Sigma_{2},\Delta_{2},\Gamma_{2},\Omega_{2},P_{2},S_{2},R_{2}(P_{2}))$
generating graph languages $L_{1}$ and $L_{2}$ respectively. Without loss of
generality we can assume that $P_{1}$ and $P_{2}$ have no elements in
common.We define a new $nc-eNCE$ graph grammar $ncG$ capable of generating the
language $L=L_{1}\oplus L_{2}$ as follows.

$ncG=(\Sigma,\Delta,\Gamma,\Omega,P,S,R(P))~{}~{}\text{where}$

,

  * $\Sigma=\Sigma_{1}\cup\Sigma_{2}\cup\\{S\\}$

  * $\Delta=\Delta_{1}\cup\Delta_{2}$

  * $\Gamma=\Gamma_{1}\cup\Gamma_{2}$

  * $\Omega=\Omega_{1}\cup\Omega_{2}$

  * $P=P_{1}\cup P_{2}\cup\\{p_{01}\\}$

  * $R(P)=p_{01}.R_{1}(P_{1}).R_{2}(P_{2})$

$p_{01}$$S$$~{}\rightarrow$$S_{1}$$S_{2}$$C_{01}=\phi$ Figure 2: Additional
Production for generation of disjoint Sum $G_{1}$$G_{2}$$\underbrace{\kern
55.00008pt}$$\underbrace{\kern 55.00008pt}$$R_{1}(P_{1})$$R_{2}(P_{2})$ Figure
3:  Schemata of Disjoint sum with graphs $G_{1}\&G_{2}$ from $L_{1}$ and
$L_{2}$ respectively.

The start graphs $S_{1}$ and $S_{2}$ of $ncG_{1}$ and $ncG_{2}$ are initially
generated using $p_{01}$. This is followed by $R_{1}(P_{1})$ generating
$G_{1}\in L_{1}$ and $R_{2}(P_{2})$ generating $G_{2}\in L_{2}$. Hence it is
clear that $R(P)$ generates $L_{1}\oplus L_{2}$. ∎

######  THeorem 3.

The class of unlabelled graph languages generated using $nc-eNCE$ graph
grammars is closed under the graph operation Kleene sum.

###### Proof.

Consider an $nc-eNCE$ graph grammar
$ncG_{1}=(\Sigma_{1},\Delta_{1},\Gamma_{1},\Omega_{1},P_{1},S_{1},$
$R_{1}(P_{1}))$ generating the graph language $L_{1}$. We define a new $nc-
eNCE$ graph grammar $ncG$ capable of generating the language
$L=L_{1}^{\oplus}$ as follows.

$ncG=(\Sigma,\Delta,\Gamma,\Omega,P,S,R(P))~{}~{}\text{where}$

,

  * $\Sigma=\Sigma_{1}\cup\\{S\\}$

  * $\Delta=\Delta_{1}$

  * $\Gamma=\Gamma_{1}$

  * $\Omega=\Omega_{1}$

  * $P=P_{1}\cup\\{p_{01},p_{02}\\}$

  * $R(P)=(p_{01}.R_{1}(P_{1}))^{*}.p_{02}$

$p_{01}$$S$$~{}\rightarrow$$S_{1}$$S$$C_{01}=\phi$$p_{02}:$$S$$~{}\rightarrow$$\varepsilon$$C_{02}=\phi$
Figure 4: Additional productions for generation of Kleene sum
$G_{1}$$G_{2}$$\cdots$$G_{n}$ Figure 5:  Schemata of Kleene sum with graphs
$G_{1},G_{2}\cdots G_{n}$ from $L_{1}$.

Initially the production $p_{01}$ replaces the start node $S$ of $ncG$ with a
copy of the start graph $S_{1}$ of $ncG_{1}$ and the node $S$ itself. Now
$R_{1}(P_{1})$ replaces $S_{1}$ by a graph $G_{1}\in L_{1}$. The rules
$p_{01}$ and $R_{1}(P_{1})$ are recursively applied to further generate new
components of the resultant graph. Finally the derivation terminates when
$p_{02}$ is applied. Hence it is clear that $R(P)$ generates $L_{1}^{\oplus}$.
∎

######  THeorem 4.

The class of underlying graph languages formed from graph classes generated
using $nc-eNCE$ jumping graph grammars is closed under the graph operation
chain concatenation.

###### Proof.

Consider two $nc-eNCE$ graph grammars
$ncG_{1}=(\Sigma_{1},\Delta_{1},\Gamma_{1},\Omega_{1},P_{1},S_{1},$
$R_{1}(P_{1}))$ and
$ncG_{2}=(\Sigma_{2},\Delta_{2},\Gamma_{2},\Omega_{2},P_{2},S_{2},R_{2}(P_{2}))$
generating graph languages $L_{1}$ and $L_{2}$ respectively. Without loss of
generality we can assume that $P_{1}$ and $P_{2}$ have no elements in common.
We begin our construction of the required grammar by carrying out the
following steps.

  1. 1.

Replace each $p_{j}^{*}$ in the regular expressions $R_{i}(P_{i})$ by the
equivalent expression $(p_{j}^{*}p_{j}+\varepsilon)$ and simplifying so that
$R_{i}(P_{i})$ is now of the form $R_{i1}(P_{i})+R_{i2}(P_{i})+\cdots
R_{in_{i}}(P_{i})$. This ensures that each $R_{ik}(P_{i})$ does not contain a
the operator ’$+$’.

  2. 2.

Initialize ${P^{\prime}}_{1}=P_{1}$. For each $R_{1k}(P_{1}),1\leq k\leq
n_{1}$, do the following

    1. (a)

Since every graph generated by $R_{1k}(P_{1})$ is non null it contains atleast
one vertex with a terminal label. Identify the last production rule $p_{1l}$
in the series $R_{1k}(P_{1})$ which has atleast one node labelled with a
terminal symbol, say ’$a$’ on the right hand side.

    2. (b)

Create a copy of $p_{1l}$ in which one occurrence of ’$a$’ is replaced by a
new terminal symbol ’$x$’, $x\notin(\Delta_{1}\cup\Delta_{2})$ and label this
production ${p^{\prime}}_{1l}$. The connection instructions corresponding to
${p^{\prime}}_{1l}$ includes all the instructions in ${p}_{1l}$. In addition
every connection instruction which contains ’$a$’ is duplicated and ’$x$’ is
inserted instead of ’$a$’. Update ${P^{\prime}}_{1}$ as
${P^{\prime}}_{1}={P^{\prime}}_{1}\cup{p^{\prime}}_{1l}$.

  3. 3.

Repeat Step 2 for $R_{2k}(P_{2}),1\leq k\leq n_{2}$ with the terminal symbol
’$b$’ on the right hand side of $p_{1l}$ replaced by $y$,
$y\notin(\Delta_{1}\cup\Delta_{2})$ label this production ${p^{\prime}}_{1l}$.
The connection instructions corresponding to ${p^{\prime}}_{1l}$ includes all
the instructions in ${p}_{1l}$. In addition every connection instruction which
contains ’$b$’ is duplicated and ’$y$’ is inserted instead of ’$b$’.One more
jumping connection instruction of the form $(y,\alpha,x)$ is added to this
set. Update ${P^{\prime}}_{2}$ as
${P^{\prime}}_{2}={P^{\prime}}_{2}\cup{p^{\prime}}_{1l}$ .

  4. 4.

Replace the last occurrence of $p_{il}$ with ${p^{\prime}}_{il}$ in each
$R_{ik}(P_{i})$ to obtain ${R^{\prime}}_{ik}(P_{i})$. The new regular control
is given by

${R^{\prime}}_{i}({P^{\prime}}_{i})={R^{\prime}}_{i1}({P^{\prime}}_{i})+{R^{\prime}}_{i2}({P^{\prime}}_{i})+\cdots{R^{\prime}}_{in_{i}}({P^{\prime}}_{i})$

.

We now define a new $nc-eNCE$ graph grammar $ncG$ capable of generating the
language $L$ such that $U(L)=U(L_{1}\odot L_{2})$ as follows.

$ncG=(\Sigma,\Delta,\Gamma,\Omega,P,S,R(P))~{}~{}\text{where}$

,

  * $\Sigma=\Sigma_{1}\cup\Sigma_{2}\cup\\{S,x,y\\}$

  * $\Delta=\Delta_{1}\cup\Delta_{2}\cup\\{x,y\\}$

  * $\Gamma=\Gamma_{1}\cup\Gamma_{2}$

  * $\Omega=\Omega_{1}\cup\Omega_{2}$

  * $P={P^{\prime}}_{1}\cup{P^{\prime}}_{2}\cup\\{p_{01}\\}$

  * $R(P)=p_{01}{R^{\prime}}_{1}({P^{\prime}}_{1}){R^{\prime}}_{2}({P^{\prime}}_{2})$

$p_{01}$$S$$~{}\rightarrow$$S_{1}$$S_{2}$$C_{01}=\phi$ Figure 6: New
Production for generation of base graph for chain concatenation.
$S$$~{}\Longrightarrow$$p_{01}$$S_{1}$$S_{2}$$\Longrightarrow$${R^{\prime}}_{1}({P^{\prime}}_{1})$$x$${G^{\prime}}_{1}$$S_{2}$$\Longrightarrow$${R^{\prime}}_{2}({P^{\prime}}_{2})$$G$${G^{\prime}}_{1}$$x$${G^{\prime}}_{2}$$y$$\alpha$
Figure 7: Schemata of chain concatenation of graphs from $L_{1}$ and
$L_{2}$using $ncG$

It is clear that the underlying graph obtained after chain concatenation of
graphs $G_{1}$ and $G_{2}$ is identical to the the underlying graph $G$ which
is the result of this construction. ∎

######  THeorem 5.

The class of underlying graph languages formed from graph classes generated
using $nc-eNCE$ jumping graph grammars is closed under the graph operation
star concatenation.

###### Proof.

Consider an $nc-eNCE$ graph grammar
$ncG_{1}=(\Sigma_{1},\Delta_{1},\Gamma_{1},\Omega_{1},P_{1},S_{1},$
$R_{1}(P_{1}))$ generating the graph language $L_{1}$. We define a new $nc-
eNCE$ graph grammar $ncG$ capable of generating the language
$L=L_{1}^{\circledast}$ as follows.

$ncG=(\Sigma,\Delta,\Gamma,\Omega,P,S,R(P))~{}~{}\text{where}$

,

  * $\Sigma=\Sigma_{1}\cup\\{S,x,c\\}$

  * $\Delta=\Delta_{1}\cup\\{x,c\\}$

  * $\Gamma=\Gamma_{1}$

  * $\Omega=\Omega_{1}$

  * $P={P^{\prime}}_{1}\cup\\{p_{01},p_{02}\\}$

  * $R(P)=(p_{01}.{R^{\prime}}_{1}({P^{\prime}}_{1}))^{*}.p_{02}$

$p_{01}$$S$$~{}\rightarrow$$S_{1}$$S$$C_{01}=\phi$$p_{02}:$$S$$~{}\rightarrow$$c$$C_{02}=\\{(c,\alpha,x)\\}$
Figure 8: Additional Productions for generation of star concatenation

Initially the production $p_{01}$ replaces the start node $S$ of $ncG$ with a
copy of the start graph $S_{1}$ of $ncG_{1}$ and the node $S$ itself. Now
${R^{\prime}}_{1}({P^{\prime}}_{1})$ replaces $S_{1}$ by a graph $G_{1}\in
L_{1}$. The rules $p_{01}$ and ${R^{\prime}}_{1}({P^{\prime}}_{1})$ are
recursively applied to further generate new components of the resultant graph.
Finally the derivation terminates when $p_{02}$ is applied. Hence it is clear
that $R(P)$ generates $L_{1}^{\circledast}$. ∎

$S$$~{}\Longrightarrow$$p_{01}$$S_{1}$$S$$~{}\Longrightarrow$${R^{\prime}}_{1}({P^{\prime}}_{1})$${G^{\prime}}_{1}$$x$$S$${G^{\prime}}_{1}$$x$${G^{\prime}}_{2}$$x$${G^{\prime}}_{3}$$x$$\Longrightarrow$$(p_{01}.{R^{\prime}}_{1}({P^{\prime}}_{1}))^{n-1}$${G^{\prime}}_{4}$${G^{\prime}}_{1}$$x$$S$$x$${G^{\prime}}_{6}$$\cdots$$x$${G^{\prime}}_{n}$$x$${G^{\prime}}_{5}$

$G$${G^{\prime}}_{1}$$x$${G^{\prime}}_{2}$$x$${G^{\prime}}_{3}$$x$$\Longrightarrow$$p_{02}$${G^{\prime}}_{4}$${G^{\prime}}_{1}$$x$$x$${G^{\prime}}_{6}$$\cdots$$c$$x$${G^{\prime}}_{n}$$x$${G^{\prime}}_{5}$

Figure 9:  Schemata of star concatenation with graphs $G_{1},G_{2}\cdots
G_{n}$ from $L_{1}$.

##  5 Conclusion

In this paper we have proved that $nc-eNCE$ graph grammars and its variants
are closed under some simple graph operations. These closure properties could
be applied in situations where we wish to generate/study the classes of graph
languages which could be recursively constructed from simpler families of
graphs. The possibility for exploration into closure properties of these
classes of grammars with respect to other operations remains open. Other
properties such as the membership problem also remain to be examined.

## References

  *   * Ehrig [1978] Ehrig, H.: Introduction to the algebraic theory of graph grammars (a survey). In: Claus, V., Ehrig, H., Rozenberg, G. (eds.) Graph-Grammars and Their Application to Computer Science and Biology, International Workshop, Bad Honnef, October 30 - November 3, 1978. Lecture Notes in Computer Science, Vol 1073, pp. 1–69. Springer, (1978)
  * Ehrig [1986] Ehrig, H.: Tutorial introduction to the algebraic approach of graph grammars. In: Ehrig, H., Nagl, M., Rosenfeld, A., Rozenberg, G. (eds.) Graph Grammars and Their Application to Computer Science. Graph Grammars 1986. Lecture Notes in Computer Science, Vol 291, pp. 3–14. Springer, (1986)
  * Ehrig et al. [1992] Ehrig, H., Habel, A., Kreowski, H.-J.: Introduction to graph grammars with applications to semantic networks. Computers & Mathematics with Applications 23(6), 557–572 (1992) https://doi.org/10.1016/0898-1221(92)90124-Z
  * Engelfriet and Vereijken [2005] Engelfriet, J., Vereijken, J.J.: Concatenation of graphs. Graph Grammars and Their Application to Computer Science. Graph Grammars 1994. Lecture Notes in Computer Science, Volume 1073, 368–382 (2005)
  * Habel and Kreowski [1986] Habel, A., Kreowski, H.: May we introduce to you: Hyperedge replacement. In: Ehrig, H., Nagl, M., Rosenfeld, A., Rozenberg, G. (eds.) Graph Grammars and Their Application to Computer Science. Graph Grammars 1986. Lecture Notes in Computer Science, Vol 291, pp. 15–26. Springer, (1986)
  * Pavlidis [1972] Pavlidis, T.: Linear and context-free graph grammars. Journal of the ACM 19(1), 11–22 (1972)
  * Rozenberg [1997] Rozenberg, G.: Node replacement graph grammars. In: Engelfriet, J., Rozenberg, G. (eds.) Handbook of Graph Grammars and Computing by Graph Transformation, pp. 1–94. World Scientific, (1997). Chap. 1
  * Rozenberg and Salomaa [1997] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages. Springer, (1997)
  * Rozenberg and Welzl [1986a] Rozenberg, G., Welzl, E.: Boundary nlc graph grammars—basic definitions, normal forms, and complexity. Information and control 69(1-3), 136–167 (1986)
  * Rozenberg and Welzl [1986b] Rozenberg, G., Welzl, E.: Graph theoretic closure properties of the family of boundary nlc graph languages. Acta informatica 23, 289–309 (1986)
  * Vijayakumar et al. [2023] Vijayakumar, J., Mathew, L., Nagar, A.K.: A new class of graph grammars and modelling of certain biological structures. Symmetry 15(2) (2023)
  * Vijayakumar and Mathew [2022] Vijayakumar, J., Mathew, L.: On jumping graph grammars. In: Proceedings of The International Conference on Mathematics of Intelligent Computing and Data Science. Springer Proceedings in Mathematics and Statistics (2022)
  * Vijayakumar and Mathew [2021] Vijayakumar, J., Mathew, L.: nc-ence graph grammars and graph rewriting p systems. In: International Conference on Membrane Computing (2021)
  * Křivka and Meduna [2015] Křivka, Z., Meduna, A.: Jumping grammars. International Journal of Foundations of Computer Science 26(06), 709–731 (2015)
  * Meduna and Zemek [2012] Meduna, A., Zemek, P.: Jumping finite automata. International Journal of Foundations of Computer Science 23(07), 1555–1578 (2012)