Weak Greibach Normal Form for Hyperedge Replacement Grammars

$\mathbb{N}$ includes $0$. The set of integers from $1$ to $n$ is denoted by $[1,n]$.

It is convenient for us to use the following notation: if $\{i_{1},\dots,i_{k}\}$ is an indexed set of integers such that for $m<n\;i_{m}<i_{n}$ holds, then it is called index-ordered and the set is denoted as $\{i_{1},\dots,i_{k}\}_{IO}$.
The set $\Sigma^{*}$ is the set of all strings over the alphabet $\Sigma$ including the empty string $\varepsilon$. The length $|w|$ of the word $w$ is the number of positions in $w$. The $i$-th symbol in $w$ is denote by $w(i)$ ($1\leq i\leq|w|$). $\Sigma^{+}$ denotes the set of all nonempty strings. The set $\Sigma^{\circledast}$ is the set of all strings consisting of distinct symbols. The set of all symbols contained in the word $w$ is denoted by $[w]$. If $f:\Sigma\to\Delta$ is a function from one set to another, then it is naturally extended as a function $f:\Sigma^{*}\to\Delta^{*}$ ($f(\sigma_{1}\dots\sigma_{k})=f(\sigma_{1})\dots f(\sigma_{k})$).

Let $C$ be some fixed set of labels, for which the function $type:C\to\mathbb{N}$ is considered.

In the remainder of the paper, hypergraphs are simply called graphs, and hyperedges are simply called edges. The set of all graphs with labels from $C$ is denoted by $\mathcal{H}(C)$. In this work, figures contain graph drawings and sketches. In drawings, nodes are depicted by black dots, edges are denotes as labeled boxes, $att$ is represented with numbered lines (called “tentacles”), external nodes are depicted by numbers in brackets. If an edge has type 2, it is depicted by an arrow. If we are not interested in a specific form of a graph but we want to have a closer look at some its part, we depict the whole graph as an area but draw its part of interest in detail.

If $G$ is a graph, and $e\in E_{G}$ is labeled by $a$, then $G$ can be denoted by $G(e:a)$.

This procedure is defined in [4]. In short, the replacement of an edge $e_{0}$ in $G$ with a graph $H$ can be done if $type(e_{0})=type(H)$ as follows:

1. 1.

   Remove $e_{0}$;

2. 2.

   Insert an isomorphic copy of $H$ (namely, $H$ and $G$ have to consist of disjoint sets of nodes and edges);

3. 3.

   For each $i$, fuse the $i$-th external node of $H$ with the $i$-th attachement node of $e_{0}$.

To be more precise, the set of edges in the resulting graph is $(E_{G}\setminus\{e_{0}\})\cup E_{H}$, and the set of nodes is $V_{G}\cup(V_{H}\setminus ext_{H})$. The result is denoted by $G[H/e_{0}]$.

Edges labeled by terminal (nonterminal) symbols are called terminal edges (nonterminal edges resp.). If a graph contains terminal edges only, it is called terminal.

If $G$ is a graph, $e_{0}\in E_{G}$, $lab(e_{0})=A$ and $\pi=A\to H\in P$, then $G$ directly derives $G[H/e_{0}]$ (we write $G\Rightarrow G[H/e_{0}]$ or $G\underset{\pi}{\Rightarrow}G[H/e_{0}]$). The transitive reflexive closure of $\Rightarrow$ is denoted by $\overset{\ast}{\Rightarrow}$. If $G\overset{\ast}{\Rightarrow}H$, then $G$ is said to derive $H$. The corresponding sequence of production applications is called a derivation.

Further we simply write $A\overset{\ast}{\Rightarrow}G$ instead of $\circledcirc(A)\overset{\ast}{\Rightarrow}G$.

Our first objective is to eliminate useless productions, productions with no edges in the right-hand side and productions with one nonterminal edge only in the right-hand side. It appears that only this step requires isolated-node boundedness. In the below transformations we provide theoretical reasonings that they can be done irregarding their algorithmic realization; however, the latter can be done similarly to the string case (see [2]).

Let $B\to G\in P$ and $E_{G}=\{e_{1},\dots,e_{n}\}$. Let $P_{1}$ contain the rules of the form $B\to G[H_{1}/e_{1}]\dots[H_{n}/e_{n}]$ where $H_{i}=\circledcirc(lab(e_{i}))$ for at least one $i$ (then replacement of $e_{i}$ by $H_{i}$ changes nothing) and $(lab(e_{i});H_{i})$ belongs to $Null$ otherwise. It is argued that $HGr^{\prime}=\langle N,\Sigma,P_{1},S\rangle$ does not have productions with edgeless right-hand sides (this follows from the construction) and that $L(HGr^{\prime})=L(HGr)$. ∎

The above procedures complete the first step of normalization.

Now we start proving Theorem 2. Let $HGr=\langle N,\Sigma,P,S\rangle$ be a grammar that generates $L$. Applying Transformations 1, 2, 3, we can assume that $HGr$ does not have useless symbols, edgeless productions and chain productions. Thus, the right-hand side of each production has at least two edges or one terminal edge.

Let us carefully examine what happens in the string case at Step 2. Consider the following

The same idea is used in the graph case. The difficulty is that we do not have the leftmost symbol in productions. However, it suffices to distinguish an arbitrary edge in the right-hand side of each production to play the role of the leftmost symbol. We do this by means of the function $\delta$.

Now $\mu(\pi)$ plays the role of the “leftmost” symbol of a production $\pi$. Then we define recursive productions as expected.

Below we study how to eliminate all the recursive $A$-productions for some fixed $A\in N$. In the string case the idea is quite simple: one moves $A$ from the beginning of the string to its end in order to invert a derivation process. Here we also exploit the idea of inverting the derivation but, of course, we have to take into account more complex and general graph structures.

Let $A\underset{\pi_{1}}{\Rightarrow}H_{1}\underset{\pi_{2}}{\Rightarrow}\dots\underset{\pi_{k}}{\Rightarrow}H_{k}$ be a $\delta$-derivation such that $lhs(\pi_{i})=A$ for $i=1,\dots,k$ and $\mu(\pi_{k})\neq A$ (compare this with the old derivation in Example 6). We provide the following intuition behind the below construction. Imagine that one has a hole in his sweater (this metaphor is related to that in [5]), and he sews it up starting from edges (i.e. he applies $\pi_{1},\dots,\pi_{k-1}$) and finishing by sewing on a patch in the center of the hole (i.e. he applies $\pi_{k}$). In the new derivation one starts with the patch (that is, the right-hand side of $\pi_{k}$), then he sews up right-hand sides of $\pi_{k-1},\dots,\pi_{2}$ in this order (thus the patch grows and becomes bigger) and finishing by connecting it with edges of the hole w.r.t. the production $\pi_{1}$ (see also Fig. 5 which provides a sketch of this process).

The major problem of this idea is the following: if we want to invert a derivation such as on Figure 5(a) and to obtain a new one, such as one drawn on Figure 5(b), we have to carefully control external nodes. Namely, in the old derivation external nodes of $H$ are predefined by $R_{1}$ while in the new derivation $R_{1}$ appears at the very last step. In order to place external nodes correctly, we introduce complex nonterminal symbols that describe how external nodes of a graph on the current derivation step correspond to external nodes of a graph on the next and on the last step. This description is done by means of partial functions.

Now we proceed with formal realization of this idea. Let $t=type(A)$. Let $\rho_{1}=A\to R_{1},\dots,\rho_{K}=A\to R_{K}$ be all the recursive $A$-productions in $P$ and let $\gamma_{1}=A\to G_{1},\dots,\gamma_{L}=A\to G_{L}$ be the remaining $A$-productions in $P$. Our goal is to construct a grammar equivalent to $HGr$ without recursive $A$-productions. Firstly, we simply remove them: $P_{1}:=P\setminus\{\rho_{1},\dots,\rho_{K}\}$. In order to compensate for the lack of these rules we add new ones accordingly to the procedure below.

Let $\gamma=\gamma_{i}$ for some $i$ and let $\rho=\rho_{j}$ for some $j$. We define $e_{0}:=\delta(\rho)$, $\widetilde{e}:=\delta(\gamma)$, $G:=rhs(\gamma)$ and $R:=rhs(\rho)$. Illustrations of these productions are presented in Fig. 1. Firstly, we extend $N$ by new nonterminal symbols of the form $(A,f,g)$ where $f,g:[1,t]\to[1,t]$ are two partial bijections; the resulting set is denoted by $N^{\prime}$. Then we add to $P_{1}$ rules of the following three forms:
Type I. Recall the metaphor about a sweater and a patch. If one imagines an $A$-labeled edge at the beginning of a derivation as a hole in a sweater, then productions of type I are designed to add a patch $G$ at the very beginning of sewing up (= of a derivation). Partial functions are used to describe what external nodes of $G$ (edges of a patch) are equal to attachment nodes of the $A$-labelled edge (edges of a hole).
Let $f,g:[1,t]\to[1,t]$ be two partial bijections. Informally, $f$ specifies what nodes of $ext_{G}$ are external on the second step of the inverted derivation (see again Fig. 5(b)); $g$ specifies what external nodes of the second step graph are external at the last step. Let $Dom(g\circ f)=\{p_{1},\dots,p_{k}\}_{IO}$. We set

• •

  $V^{\prime}:=V_{G}\cup\{u_{1},\dots,u_{t-k}\}$ for $u_{1},\dots,u_{t-k}$ being new nodes;

• •

  $E^{\prime}:=E_{G}\cup\{e^{\prime}\}$ where $e^{\prime}$ is new;

• •

  For $e\in E_{G}$ we set $att^{\prime}(e):=att_{G}(e)$ and $lab^{\prime}(e)=lab_{G}(e)$;

• •

  For $e^{\prime}$ we set $att^{\prime}(e^{\prime}):=ext_{G}u_{1}\dots u_{t-k}$;

• •

  $lab^{\prime}(e^{\prime}):=(A,f,g)$;

• •

  Let $[1,t]\setminus Ran(g\circ f)=\{j_{1},\dots,j_{t-k}\}_{IO}$ (note that $g\circ f$ is bijective so $Dom(g\circ f)$ and $Ran(g\circ f)$ are of the same size). Then we set $ext^{\prime}(i):=u_{r}$, if $i=j_{r},\;r\in\{1,\dots,t-k\}$ or $ext^{\prime}(i):=ext_{G}(p_{r})$ for $i=i_{r}=g(f(p_{r})),\;r\in\{1,\dots,k\}$.

We are ready to announce that $G^{\prime}=\langle V^{\prime},E^{\prime},att^{\prime},lab^{\prime},ext^{\prime}\rangle$. Finally, we introduce the following rule:

We define $\delta(\nu_{1,\gamma,f,g})=\delta(\gamma)$ (note that $\gamma$ is nonrecursive so is $\nu_{1,\gamma,f,g}$).

Figure 2 illustrates this type of productions.

Type II. Production of type II are used at the last step of a derivation such a on Fig. 5(b); returning to the metaphor they allow one to finish sewing up and to finally connect a patch (that has grown by applying productions of types I and III) with the edges of a hole.
We recall that $\rho=A\to R$ such that $\delta(\rho)=e_{0}\in E_{R}$ and $lab(e_{0})=A$. Let $f_{0}:[1,t]\to[1,t]$ be a function which is defined by the following relation: $f_{0}(i)=j\Leftrightarrow att_{R}(e_{0})(i)=ext_{R}(j)$. Obviously, $f_{0}$ is a partial bijection. We set

• •

  $V^{\prime}:=V_{R}$;

• •

  $E^{\prime}:=E_{G}\setminus\{e_{0}\}$;

• •

  $att^{\prime}=att_{R}|_{E^{\prime}}$, $lab^{\prime}=lab_{R}|_{E^{\prime}}$

• •

  Let $k$ be equal to $|Dom(f_{0})|$ and let $[1,t]\setminus Ran(f_{0})=\{j_{1},\dots,j_{t-k}\}_{IO}$. Then $ext^{\prime}=att_{R}(e_{0})ext_{R}(j_{1})\allowbreak\dots ext_{R}(j_{t-k})$.

We set $R^{\prime}=\langle V^{\prime},E^{\prime},att^{\prime},lab^{\prime},ext^{\prime}\rangle$. Finally, we introduce ${\nu_{2,\rho}:=(A,f_{0},id)\to R^{\prime}}$ and set ${\delta(\nu_{2,\rho}):=e}$ for some chosen $e\in E_{R^{\prime}}$ (note that there is one since $|E_{G}|\geq 2$). Here $id:[1,t]\to[1,t]$ is the identity function. See Figure 3.

Type III. Productions of type III serve to make a “sewing up step” from inside to outside. $f,g$ that specify relations between external nodes on the current step, on the next step and on the final step are changed by related functions $f^{\prime},g^{\prime}$.
Let $f,g,f^{\prime},g^{\prime}:[1,t]\to[1,t]$ be partial bijections. The whole procedure described below can be done if $g^{\prime}\circ f^{\prime}=g$.

We set

• •

  $V^{\prime}:=V_{R}\cup\{u_{1},\dots,u_{t-k^{\prime}}\}$ such that $u_{1},\dots,u_{t-k^{\prime}}$ are new nodes ($k^{\prime}$ is defined below);

• •

  $E^{\prime}:=E_{R}\setminus\{e_{0}\}\cup\{e^{\prime}\}$ where $e_{0}=\delta(\rho)$ and $e^{\prime}$ is new;

• •

  For $e\in E_{R}\setminus\{e_{0}\}$ we set $att^{\prime}(e):=att_{R}(e)$ and $lab^{\prime}(e)=lab_{R}(e)$;

• •

  For $e^{\prime}$ we set $att^{\prime}(e^{\prime}):=ext_{R}u_{1}\dots u_{t-k^{\prime}}$;

• •

  $lab^{\prime}(e^{\prime}):=(A,f^{\prime},g^{\prime})$;

• •

  Let

  • –

    $M_{1}:=Dom(g)\setminus Ran(f)=\{s_{1},\dots,s_{p}\}_{IO}$ (nodes of the current step that will be external at the last step but that were not taken into account at the previous step);

  • –

    $M_{2}:=[1,t]\setminus Ran(g\circ f)=\{j_{1},\dots,j_{t-k}\}_{IO}$;

  • –

    $g(s_{i})=j_{l_{i}}$;

  • –

    Let $M_{2}\setminus g(M_{1})=\{j_{x_{1}},\dots,j_{x_{t-k-p}}\}$ where $\{x_{1},\dots,x_{t-k-p}\}$ is index-ordered; here we note that $g(M_{1})=Ran(g)\setminus Ran(g\circ f)$, thus $g(M_{1})\subseteq M_{2}$.

  Then we set $k^{\prime}=k+p$ and

  • –

    $ext^{\prime}(i):=att_{R}(e_{0})(i)$ for $i=1,\dots,t$;

  • –

    $ext^{\prime}(t+l_{i})=ext_{R}(s_{i})$ for $i=1,\dots,p$;

  • –

    $ext^{\prime}(t+x_{i}):=u_{i}$ for $i=1,\dots,t-k^{\prime}$.