prob  Instance: Question:

# Parallel Hyperedge Replacement String Languages

Graham Campbell Supported by a Doctoral Training Grant from the Engineering
and Physical Sciences Research Council (EPSRC) Grant No. (2281162) in the
UK.School of Mathematics, Statistics and Physics, Newcastle University
Newcastle upon Tyne, United Kingdom<EMAIL_ADDRESS>
###### Abstract

There are many open questions surrounding the characterisation of groups with
context-sensitive word problem. Only in 2018 was it shown that all finitely
generated virtually Abelian groups have multiple context-free word problems,
and it is a long-standing open question as to where to place the word problems
of hyperbolic groups in the formal language hierarchy. In this paper, we
introduce a new language class called the parallel hyperedge replacement
string languages, show that it contains all multiple context-free and ET0L
languages, and lay down the foundations for future work that may be able to
place the word problems of many hyperbolic groups in this class.

##  1 Introduction

In general, the word problem is the question that asks if two strings (words)
represent the same element in some structure. In the case of groups, this is
the equivalent to asking if a given string represents the identity element,
since if $u$, $v$ are strings, then they are equal in a group if and only if
$uv^{-1}$ represents the identity in the group. Thus, given a presentation
$\langle X\mid R\rangle$ for a group $G$, the word problem is equivalent to
the membership problem for the string language
$\mathrm{WP}_{\\_}X(G)=\\{w\in(X\cup X^{-1})^{*}\mid w=_{\\_}G1_{\\_}G\\}$.
Viewing things geometrically, the word problem of a group can be identified
with the set of loops based at the identity in the Cayley graph. A partial
sketch of Cayley graphs of $\mathbb{Z}^{2}$ and $F_{\\_}2$ is provided in
Figure 1.

$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$

(a) Cayley graph of $\mathbb{Z}^{2}$

$a$$b$$a$$b$$a$$b$$b$$a$$b$$b$$a$$b$$a$$a$$b$$a$$a$$b$$b$$a$$b$$b$$a$$b$$a$$a$$b$$a$$a$$b$$a$$a$$b$$b$$a$$b$$a$$b$$a$$b$$a$$b$$a$$a$$b$$b$$a$$b$$a$$b$$a$$b$

(b) Cayley graph of $F_{\\_}2$

Figure 1: Example Cayley graphs

A natural question to ask is how hard the word problem is, in general, and for
specific families of groups. Unsurprisingly, both the universal word problem
and the word problem are undecidable in general, even for finite presentations
[26]. It is well known that a presentation defines a finite group if and only
if it admits a regular word problem [4], and defines a finitely generated
virtually free group if and only if it admits a deterministic context-free
word problem if and only if it admits a context-free word problem [23]. The
multiple context-free (MCF) languages sit strictly in between the context-free
and context-sensitive languages [30]. In 2015, a major breakthrough of Salvati
was published, showing that the word problem of $\mathbb{Z}^{2}$ is an MCF
language [29], and in 2018, Ho extended this result to all finitely generated
virtually Abelian groups [17]. This is interesting since the MCF languages are
exactly the string languages generated by hyperedge replacement grammars [11,
32]. It remains an open problem as to which other families of groups admit MCF
word problems, however, we do at least know that the fundamental group of a
hyperbolic three-manifold does not admit an MCF word problem [12].

There are of course, lots of other well-behaved language classes sitting in
between the context-free and context-sensitive classes, such as the indexed
languages [2] or the subclass of ET0L languages [28]. It is not known if there
are any groups with indexed word problems, other than the virtually free
groups, but it is known that a particular subclass of the indexed languages,
not contained in ET0L, only contains word problems of virtually free groups
[13]. We also do not know if any hyperbolic groups have ET0L word problems [7]
(other than the virtually free groups), such as the fundamental group of the
double torus. It is conjectured that every ET0L group language is admitted by
a virtually free group [7]. Figure 2 shows the (group) language hierarchy,
where necessarily strict inclusion uses a solid line, and
$\mathcal{G}\mathcal{P}$ denotes the class of all group languages (the class
of word problems of all finitely generated groups).

$\mathcal{C}\mathcal{S}$$\mathcal{I}\mathcal{N}\mathcal{D}\mathcal{E}\mathcal{X}$$\mathcal{M}\mathcal{C}\mathcal{F}$$\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}$$\mathcal{C}\mathcal{F}$$\mathcal{D}\mathcal{C}\mathcal{F}$$\mathcal{R}\mathcal{E}\mathcal{G}$

(a) String language hierarchy

$\mathcal{C}\mathcal{S}\cap\mathcal{G}\mathcal{P}$$\mathcal{I}\mathcal{N}\mathcal{D}\mathcal{E}\mathcal{X}\cap\mathcal{G}\mathcal{P}$$\mathcal{M}\mathcal{C}\mathcal{F}\cap\mathcal{G}\mathcal{P}$$\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}\cap\mathcal{G}\mathcal{P}$$\mathcal{D}\mathcal{C}\mathcal{F}\cap\mathcal{G}\mathcal{P}=\mathcal{C}\mathcal{F}\cap\mathcal{G}\mathcal{P}$$\mathcal{R}\mathcal{E}\mathcal{G}\cap\mathcal{G}\mathcal{P}$

(b) Group language hierarchy

Figure 2: Previously known formal language hierarchies

In this paper, we define and study a new string language class, combining
ideas from both ET0L and hyperedge replacement grammars. We call our new class
the parallel hyperedge replacement string (PHRS) languages, and show that the
class strictly contains both the classes of MCF and ET0L languages, that it is
a substitution and iterated substitution closed full abstract family of
languages, and that PHRS group languages are closed under free product. While
parallel hyperedge replacement has been considered before, most notably by
Habel and Kreowski (separately) [14, 19, 20], the work is not extensive and
does not consider repetition-freeness, rational control, or string
generational power. Our long term goal is to place the word problem for as
many hyperbolic groups as possible in the PHRS class. Knowledge of (geometric)
group theory and word problems is not required to read and understand this
paper - it is purely motivational!

Figure 3 summarises how the PHRS and repetition-free PHRS languages fit into
the string language hierarchy and also how we conjecture the hierarchy
collapses when we restrict to group languages.

$\mathcal{R}\mathcal{E}\mathcal{C}$$\mathcal{C}\mathcal{S}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}^{\mathrm{rf}}$$\mathcal{I}\mathcal{N}\mathcal{D}\mathcal{E}\mathcal{X}$$\mathcal{M}\mathcal{C}\mathcal{F}$$\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}$$\mathcal{C}\mathcal{F}$$\mathcal{D}\mathcal{C}\mathcal{F}$$\mathcal{R}\mathcal{E}\mathcal{G}$

(a) Proved string language hierarchy

$\mathcal{R}\mathcal{E}\mathcal{C}\cap\mathcal{G}\mathcal{P}$$\mathcal{C}\mathcal{S}\cap\mathcal{G}\mathcal{P}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}^{\mathrm{rf}}\cap\mathcal{G}\mathcal{P}\overset{\text{?}}{=}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}\cap\mathcal{G}\mathcal{P}$$\mathcal{M}\mathcal{C}\mathcal{F}\cap\mathcal{G}\mathcal{P}$$\mathcal{D}\mathcal{C}\mathcal{F}\cap\mathcal{G}\mathcal{P}\overset{\text{\char
51}}{=}\mathcal{C}\mathcal{F}\cap\mathcal{G}\mathcal{P}$$\overset{\text{?}}{=}\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}\cap\mathcal{G}\mathcal{P}\overset{\text{?}}{=}\mathcal{I}\mathcal{N}\mathcal{D}\mathcal{E}\mathcal{X}\cap\mathcal{G}\mathcal{P}$$\mathcal{R}\mathcal{E}\mathcal{G}\cap\mathcal{G}\mathcal{P}$

(b) Conjectured group language hierarchy

Figure 3: New formal language hierarchies

##  2 Preliminaries

By $\mathbb{N}$ we mean the natural numbers including zero, by $\underline{n}$
we mean $\\{1,\dots,n\\}$, and $\oplus$ denotes relational override. In this
paper, all alphabets and sequences will be finite. Formally, a sequence on a
set $S$ is a function $\sigma:\underline{n}\to S$. We view strings as
sequences on an alphabet and denote the set of all sequences on $S$ by
$S^{*}$. By a coding we mean a letter-to-letter homomorphism of free monoids,
and by a weak encoding we mean a coding which possibly sends letters to the
empty string. In this section, we define hyperedge replacement and ET0L
grammars, and recall some important known results.

###  2.1 Hyperedge Replacement

This subsection is mostly based on [14, 9]. By a signature we mean a pair
$\mathcal{C}=(\Sigma,\mathrm{type})$ where $\Sigma$ is some alphabet, called
the label set, and $\mathrm{type}:\Sigma\to\mathbb{N}$ is a typing function
which assigns to each label an arity called its type. We usually will assume
some arbitrary but fixed signature $\mathcal{C}=(\Sigma,\mathrm{type})$.

A hypergraph is a tuple
$H=(V_{\\_}H,E_{\\_}H,\textrm{att}_{\\_}H,\textrm{lab}_{\\_}H,\textrm{ext}_{\\_}H)$
where $V_{\\_}H$ is a finite set of nodes, $E_{\\_}H$ is a finite set of
hyperedges, $\textrm{att}_{\\_}H:E_{\\_}H\to V_{\\_}H^{*}$ is the attachment
function, $\textrm{lab}_{\\_}H:E_{\\_}H\to\Sigma$ is the labelling function,
and $\textrm{ext}_{\\_}H\in V_{\\_}H^{*}$ are the external nodes, such that
labelling is compatible with typing
($\textrm{type}\circ\textrm{lab}_{\\_}H=\lvert\cdot\rvert\circ\textrm{att}_{\\_}H$).
In an abuse of notation, we write
$\mathrm{type}(H)=\lvert\textrm{ext}_{\\_}H\rvert$ for the type of $H$, and
define $\textrm{type}_{\\_}H:E_{\\_}H\to\mathbb{N}$ by
$\textrm{type}_{\\_}H=\textrm{type}\circ\textrm{lab}_{\\_}H$ for the type of a
hyperedge. For any hyperedge $e\in E_{\\_}H$, whenever
$m=\mathrm{type}_{\\_}H(e)$ we call $e$ a type $m$ hyperedge, and call $e$
proper whenever $\textrm{att}_{\\_}H(e)$ is injective (contains no repeated
nodes). Call $H$ proper if every $e\in E_{\\_}H$ is proper and repetition-free
if $\textrm{ext}_{\\_}H$ is injective. The class of all hypergraphs
(repetition-free hypergraphs) over $\mathcal{C}$ is denoted
$\mathcal{H}_{\\_}\mathcal{C}$ ($\mathcal{H}_{\\_}\mathcal{C}^{\mathrm{rf}}$).
We say two hypergraphs $G,H\in\mathcal{H}_{\\_}\mathcal{C}$ are isomorphic
($G\cong H$) if there is a pair of bijective functions $(g_{\\_}V:V_{\\_}G\to
V_{\\_}H,g_{\\_}E:E_{\\_}G\to E_{\\_}H)$ such that $\textrm{att}_{\\_}H\circ
g_{\\_}E=g_{\\_}V^{*}\circ\textrm{att}_{\\_}G$, $\textrm{lab}_{\\_}H\circ
g_{\\_}E=\textrm{lab}_{\\_}G$, and
$g_{\\_}V\circ\textrm{ext}_{\\_}G=\textrm{ext}_{\\_}H$.

Given a string $w\in\Sigma^{*}$ of length $n$, its string graph is
$w^{\bullet}=$
$(\\{v_{\\_}0,\dots,v_{\\_}n\\},\\{e_{\\_}1,\dots,e_{\\_}n\\}),\mathrm{att},\mathrm{lab},v_{\\_}0v_{\\_}n)$
where $\mathrm{att}(e_{\\_}i)=v_{\\_}{i-1}v_{\\_}i$ and
$\mathrm{lab}(e_{\\_}i)=w(i)$ for all $i\in\underline{n}$ (Figure 4(a)). If
$H\cong w^{\bullet}$ for some $w\in\Sigma^{*}$, we call $H$ a string graph
representing $w$. We also use the superscript bullet to denote the handle of a
label. If $X\in\Sigma$ is of type $n$, then the handle of $X$ is the
hypergraph $X^{\bullet}=(\\{v_{\\_}1,\dots,v_{\\_}n\\},\\{e\\},$
$\mathrm{att},\mathrm{lab},v_{\\_}1\cdots v_{\\_}n)$ where
$\mathrm{att}(e)=v_{\\_}1\cdots v_{\\_}n$ and $\mathrm{lab}(e)=X$ (Figure
4(b)). These two definitions coincide for a type $2$ label, considered either
as a string of length $1$ or as a label, so there can be no confusion.

1$w(1)$$w(2)$$\cdots$$w(n)$2121212

(a) String graph $w^{\bullet}$

$X$123$\cdots$n123n

(b) Handle hypergraph $X^{\bullet}$

Figure 4: Example hypergraphs

Let $H\in\mathcal{H}_{\\_}{\mathcal{C}}$ be a hypergraph and $B\subseteq
E_{\\_}H$ be a selection of hyperedges. Then
$\sigma:B\to\mathcal{H}_{\\_}{\mathcal{C}}$ is called a replacement function
if
$\mathrm{type}\circ\sigma={\mathrm{type}_{\\_}H\\!\\!\mid_{\scaleto{B}{6pt}}}$.
The replacement of $B$ in $H$ using $\sigma$ is denoted by $H[\sigma]$, and is
the hypergraph obtained from $H$ by removing $B$ from $E_{\\_}H$, disjointly
adding the nodes and hyperedges of $\sigma(e)$, for each $e\in B$, and
identifying the $i$-th external node of $\sigma(e)$ with the $i$-th attachment
node of $e$, for each $e\in B$ and $i\in\underline{\mathrm{type}_{\\_}H(e)}$.
The external nodes of $H[\sigma]$ remain exactly those of $H$ and all
hyperedges keep their original attachments and labels. $H[\sigma]$ exists
exactly when $\sigma:B\to\mathcal{H}_{\\_}{\mathcal{C}}$ is a replacement
function, and is unique up to isomorphism. If
$B=\\{e_{\\_}1,\dots,e_{\\_}n\\}$ and $R_{\\_}i=\sigma(e_{\\_}i)$ for all
$i\in\underline{n}$, then we write
$H[e_{\\_}1/R_{\\_}1,\dots,e_{\\_}n/R_{\\_}n]$ in place of $H[\sigma]$. Figure
5 shows an example replacement.

$v_{\\_}1$1$v_{\\_}2$$e_{\\_}1$$X$$v_{\\_}3$$e_{\\_}2$$Y$$v_{\\_}4$2$e_{\\_}3$$Y$1231212

(a) Hypergraph $H$

$v_{\\_}1$1$v_{\\_}2$$e_{\\_}1$$X$$v_{\\_}3$2123

(b) Hypergraph $R$

$v_{\\_}1$1$v_{\\_}2$$e_{\\_}1$$X$$v_{\\_}3$$e_{\\_}4$$X$$v_{\\_}4$$v_{\\_}5$2$e_{\\_}3$$Y$12312312

(c) Hypergraph $H[e_{\\_}2/R]$

Figure 5: Example hyperedge replacement

Let $N\subseteq\Sigma$ be a set of non-terminals. A type $n$ rule over $N$ is
a pair $(L,R)$ with $L\in N$, $R\in\mathcal{H}_{\\_}{\mathcal{C}}$, and
$\mathrm{type}(L)=\mathrm{type}(R)=n$. Call a rule $(L,R)$ repetition-free
(proper) if $R$ is repetition-free (proper). Given a hypergraph
$H\in\mathcal{H}_{\\_}{\mathcal{C}}$ and a set of rules $\mathcal{R}$, if
$e\in E_{\\_}H$ and $(\mathrm{lab}_{\\_}H(e),R)\in\mathcal{R}$, then we say
that $H$ directly derives $H^{\prime}\cong H[e/R]$, and write
$H\Rightarrow_{\\_}{\mathcal{R}}H^{\prime}$. For a given hyperedge $e$ and
choice of rule, $H^{\prime}$ is unique up to isomorphism. Clearly
$\Rightarrow_{\\_}{\mathcal{R}}$ is a binary relation on
$\mathcal{H}_{\\_}{\mathcal{C}}$. We say $H\in\mathcal{H}_{\\_}{\mathcal{C}}$
derives $H^{\prime}$ if there is a sequence
$H\Rightarrow_{\\_}{\mathcal{R}}H_{\\_}1\Rightarrow_{\\_}{\mathcal{R}}\cdots\Rightarrow_{\\_}{\mathcal{R}}H_{\\_}k=H^{\prime}$
for some $k\geq 1$ or $H\cong H^{\prime}$. We write
$H\Rightarrow_{\\_}{\mathcal{R}}^{k}H^{\prime}$ or
$H\Rightarrow_{\\_}{\mathcal{R}}^{*}H^{\prime}$. Clearly, (direct) derivations
cannot delete nodes, and (direct) derivations made using repetition-free rules
cannot merge nodes. We have the following result for repetition-free rules:

######  Theorem 2.1 (HR Context-Freeness [14]).

Let $\mathcal{R}$ be a set of repetition-free rules over $N$,
$H\in\mathcal{H}_{\\_}{\mathcal{C}}$, $X\in N$, and $k\in\mathbb{N}$. Then
there is a derivation $X^{\bullet}\Rightarrow^{k+1}H$ if and only if there is
a rule $(X,R)\in\mathcal{R}$ and a mapping
$\sigma:\mathrm{lab}_{\\_}R^{-1}(N)\to\mathcal{H}_{\\_}{\mathcal{C}}$ such
that $H=R[\sigma]$, $\forall
e\in\mathrm{lab}_{\\_}R^{-1}(N),\mathrm{lab}_{\\_}R(e)^{\bullet}\Rightarrow^{k(e)}\sigma(e)$,
and $\sum_{\\_}{e\in\mathrm{lab}_{\\_}R^{-1}(N)}k(e)=k$.

A hyperedge replacement grammar of order $k$ ($k$-HR grammar) is a tuple
$\mathcal{G}=(\mathcal{C},N,S,\mathcal{R})$ where
$\mathcal{C}=(\Sigma,\mathrm{type})$ is a signature, $N\subseteq\Sigma$ is the
set of non-terminal labels, $S\in N$ is the start symbol, and $\mathcal{R}$ is
a finite set of rules over $N$, with $\mathrm{max}(\\{\mathrm{type}(r)\mid
r\in\mathcal{R}\\})\leq k$. We call $\Sigma\setminus N$ the terminal labels
and call $\mathcal{G}$ repetition-free (proper) if all its rules are
repetition-free (proper). The language generated by $\mathcal{G}$ is
$\mathrm{L}(\mathcal{G})=\\{H\in\mathcal{H}_{\\_}{\mathcal{C}}\mid
S^{\bullet}\Rightarrow_{\\_}{\mathcal{R}}^{*}H\textrm{ with
}\mathrm{lab}_{\\_}H^{-1}(N)=\emptyset\\}\subseteq\mathcal{H}_{\\_}{\mathcal{C}}$.
$L\subseteq\mathcal{H}_{\\_}{\mathcal{C}}$ is called a (repetition-free)
hyperedge replacement language of order $k$ ((repetition-free) $k$-HR
language) if there is a (repetition-free) $k$-HR grammar such that
$\mathrm{L}(\mathcal{G})=L$. The class of (repetition-free) HR languages is
the union of all (repetition-free) $k$-HR languages for $k\geq 0$. Denote
these $\mathcal{H}\mathcal{R}_{\\_}k$ and $\mathcal{H}\mathcal{R}$
($\mathcal{H}\mathcal{R}_{\\_}k^{\mathrm{rf}}$ and
$\mathcal{H}\mathcal{R}^{\mathrm{rf}}$). All such languages are isomorphism-
closed and homogeneous (all hypergraphs have the same type).

######  Theorem 2.2 (Repetition-Free HR Generational Power [11]).

Given an HR grammar $\mathcal{G}$ over $\mathcal{C}$, one can effectively
construct a repetition-free HR grammar $\mathcal{G}^{\prime}$ with
$\mathrm{L}(\mathcal{G}^{\prime})=\mathrm{L}(\mathcal{G})\cap\mathcal{H}_{\\_}{\mathcal{C}}^{\mathrm{rf}}$.

######  Theorem 2.3 (HR Linear-Growth [14]).

Given an infinite HR language $L$, there exists an infinite sequence of
hypergraphs in $L$, say $H_{\\_}0,H_{\\_}1,H_{\\_}2,\dots$ and constants
$c,d\in\mathbb{N}$ with $c+d\geq 1$, such that for all $i\in\mathbb{N}$,
$\lvert V_{\\_}{H_{\\_}{i+1}}\rvert=\lvert V_{\\_}{H_{\\_}{i}}\rvert+c$ and
$\lvert E_{\\_}{H_{\\_}{i+1}}\rvert=\lvert E_{\\_}{H_{\\_}{i}}\rvert+d$.

The partial function
$\mathrm{STR}:\mathcal{H}_{\\_}{\mathcal{C}}\rightharpoonup\Sigma^{*}$ sends
string graphs to the strings they represent, and is undefined elsewhere. A
language $L\subseteq\mathcal{H}_{\\_}{\mathcal{C}}$ is said to be a string
graph language if it only contains string graphs. Given an HR grammar
$\mathcal{G}$ that generates a string graph language, we write
$\mathrm{STR}(\mathrm{L}(\mathcal{G}))$ for the actual string language it
generates. A string language $L\subseteq A^{*}$ is called a (repetition-free)
hyperedge replacement string language of order $k$ ((repetition-free) $k$-HRS
language) if there is a (repetition-free) $k$-HR grammar $\mathcal{G}$ such
that $\mathcal{G}$ generates a string graph language and
$\mathrm{STR}(\mathrm{L}(\mathcal{G}))=L\setminus\\{\epsilon\\}$. The class of
(repetition-free) HRS languages is the union of all (repetition-free) $k$-HRS
languages for $k\geq 2$.

######  Theorem 2.4 (HR String Generative Power).

The following classes are equivalent, for any $k\geq 1$:

  1. 1.

$\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}^{\mathrm{rf}}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}^{\mathrm{rf}}$:
string languages of (repetition-free) hyperedge replacement grammars of order
$2k$ or $2k+1$;

  2. 2.

$\mathrm{OUT}(\mathcal{D}\mathcal{T}\mathcal{W}\mathcal{T}_{\\_}{k})$: output
languages of deterministic tree walking transducers of crossing number at most
$k$ (see [3]);

  3. 3.

$\mathcal{L}\mathcal{C}\mathcal{F}\mathcal{R}_{\\_}{k}$: string languages of
linear context-free rewriting systems of rank at most $k$ (see [31]);

  4. 4.

$\mathcal{M}\mathcal{C}\mathcal{F}_{\\_}{k}$: languages of $k$-multiple
context-free grammars (see [30]);

  5. 5.

$\mathcal{R}\mathcal{T}\mathcal{S}\mathcal{A}_{\\_}{k}$: languages of
$k$-restricted tree stack automata (see [8]).

###### Proof.

$\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{k}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{k}^{\mathrm{rf}}$
for all $k\geq 2$ is due to Theorem 2.2 and
$\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}^{\mathrm{rf}}\subseteq\mathrm{OUT}(\mathcal{D}\mathcal{T}\mathcal{W}\mathcal{T}_{\\_}{k})\subseteq\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}$
for all $k\geq 1$ is due to Engelfriet et al. [11], which gives us the
equalities in $(1)$ and $(1)=(2)$. $(2)=(3)$ is due to Weir [32], $(3)=(4)$ is
due to Seki et al. (1991) [30], and $(4)=(5)$ is due to Denkinger [8]. ∎

Call a set $S\subseteq\mathbb{N}^{d}$ linear if it is of the form
$\\{p+a_{\\_}1p_{\\_}1+\cdots a_{\\_}np_{\\_}n\mid a_{\\_}1,\dots
a_{\\_}n\in\mathbb{N}\\}$ for some fixed $p,p_{\\_}1,\dots
p_{\\_}n\in\mathbb{N}^{d}$. Call $S$ semilinear if it is a finite union of
linear sets. Given $A=\\{a_{\\_}1,\dots,a_{\\_}d\\}$ and $w\in A^{*}$, define
$\psi_{\\_}A(w)=(\lvert w\rvert_{\\_}{a_{\\_}1},\dots,\lvert
w\rvert_{\\_}{a_{\\_}d})$ where $\lvert w\rvert_{\\_}{a_{\\_}i}$ counts the
number of occurrences of $a_{\\_}i$ in $w$. A string language $L$ is called
semilinear if $\psi_{\\_}A(L)$ is semilinear. Two string languages
$L_{\\_}1,L_{\\_}2\subseteq A^{*}$ are called letter-equivalent if
$\psi_{\\_}A(L_{\\_}1)=\psi_{\\_}A(L_{\\_}2)$. In 1966, Parikh showed that a
language is semilinear if and only if it is letter-equivalent to a regular
language and that all context-free langauges are semilinear [27]. In 1991,
Seki et al. showed that all MCF languages are also semilinear and that the
classes of $k$-MCF languages are substitution closed full AFLs [30]. This
gives us the following result:

######  Theorem 2.5 (HRS Closure Properties).

For all $k\geq 2$, $\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{k}$ is a
substitution closed full AFL containing only semilinear languages.

###  2.2 ET0L Languages

Lindenmayer systems (L systems) were introduced in 1968 by Aristid
Lindenmayer. We direct the reader to [28] for a comprehensive introduction to
the topic. In this paper, we are interested in the class of string languages
called the ET0L languages, described by a specific type of L system.

A table over $\Sigma$ is a left-total finite binary relation
$T\subseteq\Sigma\times\Sigma^{*}$, and can be associated to a substitution
$\sigma_{\\_}T$ such that for any $L\subseteq\Sigma^{*}$, we define
$\sigma_{\\_}T(L)=\bigcup_{\\_}{w\in L}\sigma_{\\_}T(w)$ and
$\sigma_{\\_}T(a_{\\_}1\dots a_{\\_}n)=\\{w_{\\_}1\dots
w_{\\_}n\mid(a_{\\_}1,w_{\\_}1),\dots,(a_{\\_}n,w_{\\_}n)\in T\\}$. An ET0L
grammar is a tuple $\mathcal{G}=(\Sigma,A,S,\mathcal{T})$ where $\Sigma$ is an
alphabet, $A\subseteq\Sigma$ is the terminal alphabet, $S\in\Sigma$ is the
start symbol and $\mathcal{T}$ is a finite set of tables over $\Sigma$. The
language generated by $\mathcal{G}$ is
$\mathrm{L}(\mathcal{G})=\bigcup_{\\_}{n\in\mathbb{N}}\\{\sigma_{\\_}{T_{\\_}1}\cdots\sigma_{\\_}{T_{\\_}n}(S)\mid
T_{\\_}1,\dots,T_{\\_}n\in\mathcal{T}\\}\cap A^{*}$. A language $L\subseteq
A^{*}$ is called an ET0L language if there exists an ET0L grammar
$\mathcal{G}$ such that $\mathrm{L}(\mathcal{G})=L$. It will be convenient to
think of table entries as rules and substitutions as parallel replacement. We
will make this formal Subsection 3.1.

Finally, call an ET0L grammar propagating if each table is contained in
$\Sigma\times\Sigma^{+}$ (rather than just $\Sigma\times\Sigma^{*}$). That is,
rules have non-empty right-hand sides. The following results are useful to us:

######  Theorem 2.6 (Propagating ET0L Generative Power [28]).

Given an ET0L grammar $\mathcal{G}$, one can effectively construct a
propagating ET0L grammar $\mathcal{G}^{\prime}$ such that
$\mathrm{L}(\mathcal{G})\setminus\\{\epsilon\\}=\mathrm{L}(\mathcal{G}^{\prime})$.

######  Theorem 2.7 (ET0L Closure Properties [28]).

$\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}$ is a substitution closed full
AFL.

######  Theorem 2.8 (MCF and ET0L Incomparable).

  1. 1.

$K=\\{wh(w)\mid w\in D\\}$ is a 2-MCF language which is not ET0L, where
$D\subseteq\Sigma^{*}$ is the Dyck language [10], $\mkern
1.5mu\overline{\mkern-1.5mu\Sigma\mkern-1.5mu}\mkern 1.5mu$ is a disjoint copy
of $\Sigma$, and $h:\Sigma^{*}\to\mkern
1.5mu\overline{\mkern-1.5mu\Sigma\mkern-1.5mu}\mkern 1.5mu^{*}$ is defined by
sending each $a\in\Sigma$ to its copy $\mkern
1.5mu\overline{\mkern-1.5mua\mkern-1.5mu}\mkern 1.5mu\in\mkern
1.5mu\overline{\mkern-1.5mu\Sigma\mkern-1.5mu}\mkern 1.5mu$.

  2. 2.

$L=\\{a^{2^{n}}\mid n\in\mathbb{N}\\}$ is an ET0L language but not MCF.
Moreover, $L$ is not semilinear.

###### Proof.

The first part follows from Theorem 8 of [25]. For the second part, it is easy
to see that $\mathcal{G}=(\\{a\\},\\{a\\},a,\\{\\{(a,aa)\\}\\})$ is an ET0L
grammar with $\mathrm{L}(\mathcal{G})=L$. Recall from Subsection 2.1 that a
language is semilinear if and only if it is letter-equivalent to a regular
language. Since $L$ is a language on only one symbol, it must be semilinear if
and only if it is a regular language, but clearly, it is not a regular
language. But all MCF languages are semilinear, so it must be the case that
$L$ is not MCF. ∎

##  3 New Results

###  3.1 Parallel Hyperedge Replacement

We start by introducing parallel derivations and parallel hyperedge
replacement grammars and languages, equivalent to those defined by Habel in
Chapter VIII.3 of [14]. The most fundamental notion to us is that of a
parallel direct derivation, where every hyperedge is necessarily replaced.

In order to ensure progress can always be made, we are only interested in sets
of rules that are tables:

######  Definition 3.1 (Table).

Given $\mathcal{C}=(\Sigma,\mathrm{type})$, a table $T$ over $\Sigma$ is a
finite set of rules over $\Sigma$ such that for each $L\in\Sigma$ there is at
least one $R\in\mathcal{H}_{\\_}{\mathcal{C}}$ with $(L,R)\in T$. Call $T$
repetition-free (proper) if all its rules are repetition-free (proper).

######  Definition 3.2 (Parallel Direct Derivation).

Given $\mathcal{C}=(\Sigma,\mathrm{type})$,
$H\in\mathcal{H}_{\\_}{\mathcal{C}}$ with $E_{\\_}H=\\{e_{\\_}1,\dots
e_{\\_}n\\}$, and $T$ a table over $\Sigma$, if for each $e_{\\_}i\in
E_{\\_}H$, there is a $R_{\\_}i\in\mathcal{H}_{\\_}{\mathcal{C}}$ such that
$(\mathrm{lab}_{\\_}H(e_{\\_}i),R_{\\_}i)\in T$, then we say that $H$
parallelly directly derives $H^{\prime}\cong
H[e_{\\_}1/R_{\\_}1,\dots,e_{\\_}n/R_{\\_}n]$, and write
$H\Rrightarrow_{\\_}{T}H^{\prime}$.

######  Definition 3.3 (Parallel Derivation).

Given $\mathcal{C}=(\Sigma,\mathrm{type})$,
$H,H^{\prime}\in\mathcal{H}_{\\_}{\mathcal{C}}$, and a finite set of tables
$\mathcal{T}=\\{T_{\\_}i\mid i\in I\\}$ over $\Sigma$ indexed by $I$, we say
$H$ parallelly derives $H^{\prime}$ if there is a sequence of parallel direct
derivations
$H\Rrightarrow_{\\_}{T_{\\_}{{i_{\\_}1}}}H_{\\_}1\Rrightarrow_{\\_}{T_{\\_}{i_{\\_}2}}\cdots\Rrightarrow_{\\_}{T_{\\_}{i_{\\_}k}}H_{\\_}k=H^{\prime}$
or $H\cong H^{\prime}$. We write
$H\Rrightarrow_{\\_}{\mathcal{T}}^{i_{\\_}1i_{\\_}2\cdots
i_{\\_}k}H^{\prime}$, $H\Rrightarrow_{\\_}{\mathcal{T}}^{k}H^{\prime}$, or
$H\Rrightarrow_{\\_}{\mathcal{T}}^{*}H^{\prime}$. Call $i_{\\_}1i_{\\_}2\cdots
i_{\\_}k\in I^{*}$ the trace of the derivation, defined to be $\epsilon$ when
$H\cong H^{\prime}$.

Rather than replacing only non-terminals, as is usual in hyperedge replacement
grammars, we allow all hyperedges to be replaced, and have a special set of
terminal symbols to allow us to say when it is that a hypergraph is terminally
labelled, just like ET0L grammars.

######  Definition 3.4 (PHR Grammar).

A parallel hyperedge replacement grammar of order $k$ ($k$-PHR grammar) is a
tuple $\mathcal{G}=(\mathcal{C},A,S,\mathcal{T})$ where
$\mathcal{C}=(\Sigma,\mathrm{type})$ is a signature, $A\subseteq\Sigma$ is the
set of terminal labels, $S\in\Sigma$ is the start symbol, and
$\mathcal{T}=\\{T_{\\_}i\mid i\in I\\}$ is a non-empty, finite set of tables
over $\Sigma$ indexed by $I$ with $\mathrm{max}(\\{\mathrm{type}(r)\mid
r\in\bigcup_{\\_}{T_{\\_}i\in\mathcal{T}}T_{\\_}i\\})\leq k$. We call
$\Sigma\setminus N$ the terminal labels and call $\mathcal{G}$ repetition-free
(proper) if all its tables are repetition-free (proper). The language
generated by $\mathcal{G}$ is
$\mathrm{L}(\mathcal{G})=\\{H\in\mathcal{H}_{\\_}{\mathcal{C}}\mid
S^{\bullet}\Rrightarrow_{\\_}{\mathcal{T}}^{*}H\textrm{ with
}\mathrm{lab}_{\\_}H^{-1}(A)=E_{\\_}H\\}\subseteq\mathcal{H}_{\\_}{\mathcal{C}}$.

######  Definition 3.5 (PHR Language).

$L\subseteq\mathcal{H}_{\\_}{\mathcal{C}}$ is called a (repetition-free)
parallel hyperedge replacement language of order $k$ ((repetition-free)
$k$-PHR language) if there is a (repetition-free) $k$-PHR grammar
$\mathcal{G}$ such that $\mathrm{L}(\mathcal{G})=L$. The class of (repetition-
free) PHR languages is the union of all (repetition-free) $k$-PHR languages
for $k\geq 0$. Denote these $\mathcal{P}\mathcal{H}\mathcal{R}_{\\_}k$ and
$\mathcal{P}\mathcal{H}\mathcal{R}$
($\mathcal{P}\mathcal{H}\mathcal{R}_{\\_}k^{\mathrm{rf}}$ and
$\mathcal{P}\mathcal{H}\mathcal{R}^{\mathrm{rf}}$).

Just like languages generated by hyperedge replacement, parallel hyperedge
replacement languages are closed under hypergraph isomorphism and are
homogeneous in the sense that all hypergraphs in a language have the same
type. Next, we confirm that PHR languages strictly contain the HR languages:

######  Theorem 3.6 (PHR Generalises HR).

For all $k\geq 0$,
$\mathcal{H}\mathcal{R}_{\\_}{k}\subsetneq\mathcal{P}\mathcal{H}\mathcal{R}_{\\_}{k}$
and
$\mathcal{H}\mathcal{R}_{\\_}{k}^{\mathrm{rf}}\subsetneq\mathcal{P}\mathcal{H}\mathcal{R}_{\\_}{k}^{\mathrm{rf}}$.

###### Proof.

Suppose $\mathcal{C}=(\Sigma,\mathrm{type})$ and
$\mathcal{G}=(\mathcal{C},N,S,\\{r_{\\_}1,\dots,r_{\\_}n\\})$ is a
(repetition-free) $k$-HR grammar. Then we construct a (repetition-free)
$k$-PHR grammar $\mathcal{G}^{\prime}=(\mathcal{C},A,S,\mathcal{T})$ with
$A=\Sigma\setminus N$ and $\mathcal{T}=\\{T_{\\_}1\\}$ where
$T_{\\_}1=\\{r_{\\_}1,\dots,r_{\\_}n\\}\cup\\{(X,X^{\bullet})\mid
X\in\Sigma\\}$. Clearly every parallel direct derivation with start hypergraph
$G$ can be decomposed into at most $\lvert E_{\\_}G\rvert$ direct derivations
where if an edge is replaced by itself, we omit it, and if a genuine
replacement from $\mathcal{R}$ occurs, we use that. So, by induction on
derivation length, we see that every parallel derivation in
$\mathcal{G}^{\prime}$ can actually be written as a derivation in
$\mathcal{G}$. Similarly, every direct derivation in $\mathcal{G}$ can be
lifted to a parallel derivation in $\mathcal{G}^{\prime}$ by replacing all but
one edge by itself. So, by induction on derivation length, we see that every
derivation in $\mathcal{G}$ can be written as a parallel derivation in
$\mathcal{G}^{\prime}$. Thus, together with the fact that the terminal symbols
and start symbol coincide,
$\mathrm{L}(\mathcal{G})=\mathrm{L}(\mathcal{G}^{\prime})$.

To see strictness, we are inspired by the fact that the string language
$\\{a^{2^{n}}\mid n\in\mathbb{N}\\}$ is ET0L but not MCF (Theorem 2.8). We
will show there is a repetition-free $0$-PHR language that is not $k$-HR for
any $k\geq 0$. Let $\mathcal{G}=(\mathcal{C},A,S,\mathcal{T})$ be the
repetition-free $0$-PHR grammar with
$\mathcal{C}=(\\{\square\\},\\{(\square,0)\\})$, $A=\\{\square\\}$,
$S=\square$, and $\mathcal{T}=\\{T_{\\_}1\\}$ where
$T_{\\_}1=\\{(\square,\square^{\bullet}\sqcup\square^{\bullet})\\}$ ($\sqcup$
denotes disjoint union of hypergraphs). Clearly $\mathrm{L}(\mathcal{G})$ is
the language of hypergraphs over $\mathcal{C}$ with $2^{n}$ hyperedges. By
Theorem 2.3, $\mathrm{L}(\mathcal{G})$ is not HR. ∎

######  Corollary 3.7.

PHR languages need not have only linear growth, in the sense of Theorem 2.3.

Figure 6 shows an example derivation using the grammar from the proof of
Theorem 3.6.

$\square$$\Rrightarrow$$\square$$\square$$\Rrightarrow$$\square$$\square$$\square$$\square$$\Rrightarrow$$\square$$\square$$\square$$\square$$\square$$\square$$\square$$\square$

Figure 6: Example parallel derivation

###  3.2 Rational Control of Traces

It is often convenient to restrict the sequences of allowed traces when
defining a language using a PHR grammar, leading to better readability of
grammars and possibly shorter proofs. A popular choice in L systems is so-
called rational control, and was considered for ET0L in 1975 by Nielsen [24]
and later by Asveld [5]. We will make precise a notion of rational control for
PHR grammars, and show that generational power actually remains the same
because we can always encode the rational control.

######  Definition 3.8 (Controlled Parallel Derivation).

Given $\mathcal{C}=(\Sigma,\mathrm{type})$,
$H,H^{\prime}\in\mathcal{H}_{\\_}{\mathcal{C}}$, a finite set of tables
$\mathcal{T}=\\{T_{\\_}i\mid i\in I\\}$ over $\Sigma$ indexed by $I$, and
$\mathcal{M}$ an FSA over $I$, we say $H$ ($\mathcal{M}$-)parallelly derives
$H^{\prime}$ if $H$ parallelly derives $H^{\prime}$ with trace
$i_{\\_}1i_{\\_}2\cdots i_{\\_}k\in\mathrm{L}(\mathcal{M})$. We write
$H\Rrightarrow_{\\_}{\mathcal{T}}^{i_{\\_}1i_{\\_}2\cdots
i_{\\_}k}H^{\prime}$, $H\Rrightarrow_{\\_}{\mathcal{T}}^{k}H^{\prime}$, or
$H\Rrightarrow_{\\_}{\mathcal{T}}^{\mathcal{M}}H^{\prime}$.

######  Definition 3.9 (PHR Grammar with Control).

A (repetition-free) parallel hyperedge replacement grammar with control of
order $k$ ((repetition-free) $k$-PHR grammar with control) is a tuple
$\mathcal{G}=(\mathcal{C},A,S,\mathcal{T},\mathcal{M})$ where
$(\mathcal{C},A,S,\mathcal{T})$ is a (repetition-free) $k$-PHR grammar (called
the underlying grammar) with $\mathcal{T}$ indexed by $I$, and $\mathcal{M}$
is an FSA over $I$ (called the rational control). The generated language is
$\mathrm{L}(\mathcal{G})=\\{H\in\mathcal{H}_{\\_}{\mathcal{C}}\mid
S^{\bullet}\Rrightarrow_{\\_}{\mathcal{T}}^{\mathcal{M}}H\textrm{ with
}\mathrm{lab}_{\\_}H^{-1}(A)=E_{\\_}H\\}\subseteq\mathcal{H}_{\\_}{\mathcal{C}}$.

######  Theorem 3.10 (PHR Grammar Control Removal).

Given a (repetition-free) $k$-PHR grammar with control $\mathcal{G}$, one can
effectively construct a (repetition-free) $k$-PHR grammar
$\mathcal{G}^{\prime}$ such that
$\mathrm{L}(\mathcal{G})=\mathrm{L}(\mathcal{G}^{\prime})$.

###### Proof.

Let $\mathcal{G}=((\Sigma,\mathrm{type}),A,S,\\{T_{\\_}1,\dots
T_{\\_}l\\},\mathcal{M})$. Without loss of generality, we can assume that
$\mathcal{M}=(Q,\underline{n},\delta,i,F))$ is deterministic and full, and
$Q\cap\Sigma=\emptyset$. We construct the (repetition-free) $k$-PHR grammar
$\mathcal{G}^{\prime}=((\Sigma^{\prime},\mathrm{type}^{\prime}),A,S^{\prime},\mathcal{T}^{\prime})$.
First, make a disjoint (from $\Sigma_{\\_}1$) copy of $A$, $\mkern
1.5mu\overline{\mkern-1.5muA\mkern-1.5mu}\mkern 1.5mu$, and to each $X\in A$,
associate a unique $\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu\in\mkern 1.5mu\overline{\mkern-1.5muA\mkern-1.5mu}\mkern 1.5mu$.
Moreover, given a hypergraph $H$, denote by $\mkern
1.5mu\overline{\mkern-1.5muH\mkern-1.5mu}\mkern 1.5mu$ the same hypergraph but
with its labelling function composed with the function that sends $X\in A$ to
$\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu$ and leaves
everything else in place. Next, choose some additional fresh symbols:
$S^{\prime}$, $F_{\\_}0,\dots,F_{\\_}k$. Using these, we define
$\Sigma^{\prime}=\\{S^{\prime}\\}\cup Q\cup\Sigma\cup\mkern
1.5mu\overline{\mkern-1.5muA\mkern-1.5mu}\mkern
1.5mu\cup\\{F_{\\_}0,\dots,F_{\\_}l\\}$ where
$\mathrm{type}(S^{\prime})=\mathrm{type}(S)$, $\mathrm{type}(q)=0$ for all
$q\in Q$, $\mathrm{type}^{\prime}(X)=\mathrm{type}(X)$ for all $X\in\Sigma$,
$\mathrm{type}^{\prime}(\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)=\mathrm{type}(X)$ for all $X\in A$, and
$\mathrm{type}^{\prime}(F_{\\_}j)=j$ for all $j\in\underline{k}$.

Finally, let
$\mathcal{T}^{\prime}=\\{T^{\prime}_{\\_}{0},T^{\prime}_{\\_}1,\dots
T^{\prime}_{\\_}l\\}$ where $T^{\prime}_{\\_}0=\\{(S^{\prime},\mkern
1.5mu\overline{\mkern-1.5muS^{\bullet}\mkern-1.5mu}\mkern 1.5mu\sqcup
i^{\bullet})\\}\cup\\{(q,\emptyset)\mid q\in F\\}\cup\\{(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu,X^{\bullet})\mid X\in
A\\}\cup\\{(X,F_{\\_}{\mathrm{type}^{\prime}(X)})\mid X\in(Q\setminus
F)\cup\Sigma\cup\\{F_{\\_}0,\dots,F_{\\_}k\\}\\}$ and for each
$j\in\underline{l}$, $T^{\prime}_{\\_}j=\\{(\mkern
1.5mu\overline{\mkern-1.5muL\mkern-1.5mu}\mkern 1.5mu,\mkern
1.5mu\overline{\mkern-1.5muR\mkern-1.5mu}\mkern 1.5mu)\mid(L,R)\in
T_{\\_}j\land L\in A\\}\cup\\{(L,\mkern
1.5mu\overline{\mkern-1.5muR\mkern-1.5mu}\mkern 1.5mu)\mid(L,R)\in
T_{\\_}j\land L\not\in A\\}\cup\\{(q,\delta(q,j)^{\bullet})\mid q\in
Q\\}\cup\\{(X,X^{\bullet})\mid X\in\\{S^{\prime}\\}\cup A\cup\\{F_{\\_}0,\dots
F_{\\_}k\\}\\}$.

We can see that the purpose of table $0$ is to start and stop the derivation
process, with the rest of the tables simulating the original system, while
also simulating the automaton. So, if
$S^{\bullet}\Rrightarrow_{\\_}{\mathcal{T}}^{w}H$ is a derivation in
$\mathcal{G}$ with $H$ terminally labelled and $w\in\mathrm{L}(\mathcal{M})$,
then there is a corresponding derivation
$S^{\prime\bullet}\Rrightarrow_{\\_}{\mathcal{T}}^{0w0}H$ in
$\mathcal{G}^{\prime}$. That is
$\mathrm{L}(\mathcal{G})\subseteq\mathrm{L}(\mathcal{G}^{\prime})$. To see the
reverse inclusion, we analyse all derivations of the form
$S^{\prime\bullet}\Rrightarrow_{\\_}{\mathcal{T}}^{w}H$. If $w$ does not
contain $0$ at least twice, then $H$ is necessarily not terminally labelled.
So, useful derivations must have trace $x0y0z$ where $x,y\in\\{1,\dots
l\\}^{*}$, $z\in\\{0,\dots l\\}^{*}$. Clearly if
$S^{\prime\bullet}\Rrightarrow_{\\_}{\mathcal{T}}^{x}H^{\prime}$, then
$H^{\prime}\cong S^{\prime\bullet}$, so we can assume $x=\epsilon$. Similarly,
if $S^{\prime\bullet}\Rrightarrow_{\\_}{\mathcal{T}}^{0y0}H^{\prime}$ and
$H^{\prime}\Rrightarrow_{\\_}{\mathcal{T}}^{z}H$, then either $H^{\prime}\cong
H$ if $H$ was terminally labelled, and so we could assume $z=\epsilon$, or
$H^{\prime}$ is labelled by at least non-terminal which has no terminally
labelled successor hypergraph, and so it doesn’t matter what $H$ is. Finally,
we analyse $y$. If $y\in\mathrm{L}(\mathcal{M})$, then we proceed as in the
analysis of the other direction of inclusion. If
$y\not\in\mathrm{L}(\mathcal{M})$, then the final step sends the type zero
symbol tracking the machine state to $F_{\\_}0$ which forces all successors of
the hypergraph to be not terminally labelled. ∎

Thus, the hypergraph languages that can be generated by $k$-PHR grammars are
exactly those that can be generated by $k$-PHR grammars with control, since
certainly no control can be simulated.

###  3.3 PHRS Languages

We now turn our attention to string languages. We believe the class of
parallel hyperedge replacement string languages is a genuinely new class of
languages, containing all multiple context-free and ET0L languages. It is not
simply equal to the (parallel) multiple context-free languages because these
are known to be incomparable with ET0L [25]. Recall that the hyperedge
replacement string languages are exactly the multiple context-free languages.
In this subsection, we confirm that parallel hyperedge replacement string
languages contain all of these and also all of the ET0L languages.

######  Definition 3.11 (PHR String Language).

A string language $L\subseteq A^{*}$ is called a (repetition-free) parallel
hyperedge replacement string language of order $k$ ((repetition-free) $k$-PHRS
language) if there is a (repetition-free) $k$-PHR grammar $\mathcal{G}$ such
that $\mathcal{G}$ generates a string graph language and
$\mathrm{STR}(\mathrm{L}(\mathcal{G}))=L\setminus\\{\epsilon\\}$. The class of
(repetition-free) PHRS languages is the union of all (repetition-free)
$k$-PHRS languages for $k\geq 2$. Denote these
$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k$ and
$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}$
($\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}$ and
$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}^{\mathrm{rf}}$).

Notice that we exclude the case $k<2$, since
$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}0^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}0=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}1^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}1=\\{\emptyset,\\{\epsilon\\}\\}$.
It is clear that
$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}\subseteq\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k$
for $k\geq 2$, and that we can iteratively compute the unreachable symbols in
a similar way as for context-free grammars (see Section 7.1 of [18]):

######  Definition 3.12 (Unreachable Symbol).

Given a PHR grammar over $(\Sigma,\mathrm{type})$, $X\in\Sigma$ is called
unreachable if there is no derivation starting at $S^{\bullet}$ containing a
hypergraph with a hyperedge labelled by $X$.

######  Lemma 3.13.

For $k\geq 2$, given a (repetition-free) $k$-PHR grammar $\mathcal{G}$, one
can effectively construct a (repetition-free) $k$-PHR grammar
$\mathcal{G}^{\prime}$ with no unreachable symbols and
$\mathrm{L}(\mathcal{G})=\mathrm{L}(\mathcal{G}^{\prime})$.

The following lemma is also clear, using Lemma 3.13, enabling us to prove
Theorem 3.15:

######  Lemma 3.14.

For $k\geq 2$, given a $k$-PHR grammar $\mathcal{G}$ generating a string graph
language, one can effectively construct a proper $k$-PHR grammar
$\mathcal{G}^{\prime}$ such that there are no unreachable symbols, all
terminals are type $2$, all non-terminals are type at least $2$, and
$\mathrm{L}(\mathcal{G})=\mathrm{L}(\mathcal{G}^{\prime})$.

######  Theorem 3.15 (PHRS Generalises ET0L).

For all $k\geq 2$,
$\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}\subseteq\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}$.
When $k\geq 4$,
$\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}\subsetneq\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}$.
Moreover,
$\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2$.

###### Proof.

First we show
$\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}\subseteq\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}$
for all $k\geq 2$. Suppose $L$ is an ET0L language, then by Theorem 2.6, there
exists a propagating ET0L grammar $\mathcal{G}=(\Sigma,A,S,\\{T_{\\_}i\mid
i\in I\\})$ such that $L\setminus\\{\epsilon\\}=\mathrm{L}(\mathcal{G})$. It
follows that every rule can be encoded as an HR rule over
$\mathcal{C}^{\prime}=(\Sigma,\Sigma\times\\{2\\})$ giving us a repetition-
free $2$-PHR grammar
$\mathcal{G}^{\prime}=(\mathcal{C}^{\prime},A,S,\\{\\{(L,R^{\bullet})\mid(L,R)\in
T_{\\_}i\\}\mid i\in I\\})$ with
$\mathrm{L}(\mathcal{G})=\mathrm{STR}(\mathrm{L}(\mathcal{G}^{\prime}))$.

Next, we show that
$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2\subseteq\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}$.
Suppose $L$ is a $2$-PHRS language, then there is a $2$-PHR grammar
$\mathcal{G}=(\mathcal{C},A,S,\\{T_{\\_}i\mid i\in I\\})$ generating a string
graph language such that
$L\setminus\\{\epsilon\\}=\mathrm{STR}(\mathrm{L}(\mathcal{G}))$. Lemma 3.14
allows us to assume a lot about the form of RHSs of rules. It is easy to see
that all RHSs must actually be string graphs, or could be transformed to
string graphs, since any non-conformant pieces can just be inlined into the
string graph because it will ultimately be deleted and the nodes merged in any
terminally labelled derived hypergraph. So the system can be converted into an
ET0L grammar. Thus, we have
$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2}\subseteq\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}\subseteq\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2}^{\mathrm{rf}}$
and
$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2}^{\mathrm{rf}}\subseteq\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2}$,
so the inclusions must be equalities.

Finally, strictness follows from Theorems 2.4, 2.8, and 3.6. That is, we can
construct a repetition-free $4$-PHR grammar $\mathcal{G}^{\prime}$ generating
a string graph language with
$\mathrm{STR}(\mathrm{L}(\mathcal{G}^{\prime}))=K\setminus\\{\epsilon\\}$
(from Theorem 2.8) which is not ET0L. ∎

######  Corollary 3.16.

There are repetition-free $2$-PHRS languages that are not semilinear.

###### Proof.

Theorem 3.15 gives us a $2$-PHRS language which is not semilinear by Theorem
2.8. ∎

######  Theorem 3.17 (PHRS Generalises MCF).

For all $k\geq 2$,
$\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}\subsetneq\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}$.

###### Proof.

Inclusion from Theorem 2.4, and Theorem 3.6 and its proof. We get strictness
from Theorem 2.8 together with Theorem 3.15. ∎

###  3.4 Formal Language Closure Properties

Recall that a full AFL is a non-empty class of string languages closed under
rational operations (union, concatenation, Kleene plus), rational
intersection, homomorphisms, and inverse homomorphisms. In this subsection, we
show that the class of PHRS languages is an (iterated) substitution closed
full AFL, and that the class of repetition-free PHRS languages is closed under
non-erasing (iterated) substitution with closure under rational operations and
non-erasing homomorphisms following from this as a corollary.

######  Theorem 3.18 (PHRS Closed Under Substitutions).

Let $L\subseteq A^{*}$ be a $k$-PHRS language (repetition-free $k$-PHRS
language) and $h$ be a $k$-PHRS substitution (non-erasing repetition-free
$k$-PHRS substitution) on $A$. Then $h(L)$ and
$\bigcup_{\\_}{n\in\mathbb{N}}h^{n}(L)$ are $k$-PHRS languages (repetition-
free $k$-PHRS languages).

###### Proof.

There is a (repetition-free) $k$-PHR grammar
$\mathcal{G}=(\mathcal{C},A,S,\mathcal{T})$ such that
$A=\\{a_{\\_}1,\dots,a_{\\_}m\\}$ and $\mathrm{L}(\mathcal{G})$ is a string
graph language, and
$\mathrm{STR}(\mathrm{L}(\mathcal{G}))=L\setminus\\{\epsilon\\}$. Similarly
for each $i\in\underline{m}$, there is a (repetition-free) $k$-PHR grammar
$\mathcal{G}_{\\_}i=(\mathcal{C}_{\\_}i,B,S_{\\_}i,\mathcal{T}_{\\_}i)$ such
that $\mathrm{L}(\mathcal{G})$ is a string graph language and
$\mathrm{STR}(\mathrm{L}(\mathcal{G}_{\\_}i))=h(a_{\\_}i)$. Without loss of
generality, we assume both that each $S_{\\_}i$ does not appear as a label in
any RHS apart from possibly a rule $(S_{\\_}i,S_{\\_}i^{\bullet})$ and that
the following sets are pairwise disjoint: $\Sigma,B,\Sigma_{\\_}1\setminus
B,\dots,\Sigma_{\\_}m\setminus B$. For each $i\in\underline{m}$, let $\mkern
1.5mu\overline{\mkern-1.5mu\Sigma_{\\_}i\mkern-1.5mu}\mkern 1.5mu$ be a copy
of $\Sigma_{\\_}i$ consisting of fresh symbols, and identify each
$x\in\Sigma_{\\_}i$ with its copy $\mkern
1.5mu\overline{\mkern-1.5mux\mkern-1.5mu}\mkern 1.5mu\in\mkern
1.5mu\overline{\mkern-1.5mu\Sigma_{\\_}i\mkern-1.5mu}\mkern 1.5mu$. Given a
hypergraph $H$, by $\mkern 1.5mu\overline{\mkern-1.5muH\mkern-1.5mu}\mkern
1.5mu$ we mean $H$ but with its labelled function composed with the function
which takes any $x\in\Sigma_{\\_}i$ to $\mkern
1.5mu\overline{\mkern-1.5mux\mkern-1.5mu}\mkern 1.5mu$ and leaves everything
else fixed.

We now construct the (repetition-free) $k$-PHR grammar
$\mathcal{G}^{\prime}=(\mathcal{C}^{\prime},B,\mathcal{T}^{\prime},S)$ such
that $\mathrm{L}(\mathcal{G}^{\prime})$ is a string graph language and
$\mathrm{STR}(\mathrm{L}(\mathcal{G}^{\prime}))=h(L)\setminus\\{\epsilon\\}$.
Let $\mathcal{C}^{\prime}=(\Sigma^{\prime},\mathrm{type}^{\prime})$ be the
union of all the above signatures also including the disjoint copies, where
copies are of the same type as their original symbols, together with the fresh
symbols $F_{\\_}0,\dots F_{\\_}k$ of type $0,\dots,k$, respectively. Finally,
let $\mathcal{R}=\\{(X,X^{\bullet})\mid X\in\Sigma^{\prime}\\}$,
$\mathcal{F}=\\{(X,F_{\\_}{\mathrm{type}^{\prime}(X)}^{\bullet})\mid
X\in\Sigma^{\prime}\\}$, and $\mathcal{T}^{\prime}=\bigcup_{\\_}{0\leq i\leq
m}\mathcal{T}^{\prime}_{\\_}i$, where
$\mathcal{T}^{\prime}_{\\_}0=\\{\mathcal{R}\oplus T\mid
T\in\mathcal{T}\\}\cup\\{\mathcal{F}\oplus\\{(a_{\\_}i,\mkern
1.5mu\overline{\mkern-1.5muS_{\\_}i\mkern-1.5mu}\mkern 1.5mu^{\bullet})\mid
i\in\underline{m}\\}\\}$, and for each $i\in\underline{m}$ let
$\mathcal{T}_{\\_}i=\\{\mathcal{R}\oplus(\\{(\mkern
1.5mu\overline{\mkern-1.5muL\mkern-1.5mu}\mkern 1.5mu,\mkern
1.5mu\overline{\mkern-1.5muR\mkern-1.5mu}\mkern 1.5mu)\mid(L,R)\in
T\\}\cup\\{(\mkern 1.5mu\overline{\mkern-1.5muS_{\\_}i\mkern-1.5mu}\mkern
1.5mu,\mkern 1.5mu\overline{\mkern-1.5muS_{\\_}i\mkern-1.5mu}\mkern
1.5mu^{\bullet})\\})\mid
T\in\mathcal{T}_{\\_}i\\}\cup\\{\mathcal{R}\oplus(\\{(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu,X^{\bullet})\mid X\in
B\\}\cup\\{(\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu,F_{\\_}{\mathrm{type}^{\prime}(X)}^{\bullet})\mid
X\in\Sigma_{\\_}i\setminus(B\cup\\{\mkern
1.5mu\overline{\mkern-1.5muS_{\\_}i\mkern-1.5mu}\mkern 1.5mu\\})\\})\\}$.

One can see that derivations that make progress start with $S^{\bullet}$ then
apply tables from the first part of $\mathcal{T}^{\prime}_{\\_}0$, simulating
$\mathcal{G}$. At some point, the final table of $\mathcal{T}^{\prime}_{\\_}0$
may be applied, which immediately rewrites all the terminals to encoded start
symbols for their respective grammars for substitution and sends all non-
terminals to failure non-terminals. If a hypergraph contains any failure non-
terminals at this point, non terminally labelled hypergraph can be derived in
future. Derivations can now simulate the $\mathcal{G}_{\\_}i$ totally
independently, with choice of delaying start, giving total freedom over the
simulated derivation sequences for each instance of the encoded start symbol.
Finally, the encoded systems can end their simulation at any point by sending
their encoded terminals to real terminals in $B$ and their encoded non-
terminals to failure non-terminals. It is now clear that
$\mathrm{STR}(\mathrm{L}(\mathcal{G}^{\prime}))=h(L)\setminus\\{\epsilon\\}$,
as required.

Showing $\bigcup_{\\_}{n\in\mathbb{N}}h^{n}(L)$ is similar, modifying the
above proof, adding another table which can be used to send all terminals to
restart the process and all non-terminals to a failure symbol. ∎

######  Corollary 3.19 (PHRS Closed Under Homomorphisms).

Let $L\subseteq A^{*}$ be a $k$-PHRS language (repetition-free $k$-PHRS
language) for any $k\geq 2$ and $\varphi:A^{*}\to B^{*}$ be a homomorphism
(non-erasing homomorphism). Then $\varphi(L)$ is a $k$-PHRS language
(repetition-free $k$-PHRS language).

Next, we show closure under rational operations, which can be seen via the
following general result:

######  Lemma 3.20.

Let $\mathcal{F}$ be a class of string languages containing all regular
languages, which is closed under non-erasing substitution. Let
$L_{\\_}1,L_{\\_}2\subseteq A_{\\_}1^{*}$ be $\mathcal{F}$ languages. Then:

  1. 1.

$L_{\\_}1\cup L_{\\_}2$ is an $\mathcal{F}$ language; 8cm (closure under
union)

  2. 2.

$L_{\\_}1L_{\\_}2$ is an $\mathcal{F}$ language; 8cm (closure under
concatenation)

  3. 3.

$L_{\\_}1^{+}$ is an $\mathcal{F}$ language. 8cm (closure under Kleene plus)

###### Proof.

To see (1), notice that $L_{\\_}1\cup L_{\\_}2$ is simply $h(K)$ where
$K=\text{ \text@underline{if} }\epsilon\in L_{\\_}1\cup L_{\\_}2\text{
\text@underline{then} }\\{X,Y,\epsilon\\}\text{ \text@underline{else}
}\\{X,Y\\}$, and $h$ is a non-erasing substitution with
$h(X)=L_{\\_}1\setminus\\{\epsilon\\}$ and
$h(Y)=L_{\\_}2\setminus\\{\epsilon\\}$. Thus we have $L_{\\_}1\cup
L_{\\_}2=h(K)$, and since, in either case, $K$ is a regular language,
$h(K)\in\mathcal{F}$. (2) and (3) are similar. ∎

######  Theorem 3.21 (PHRS Closed Under Rational Operations).

Let $L_{\\_}1,L_{\\_}2\subseteq A_{\\_}1^{*}$ be (repetition-free) $k$-PHRS
languages for any $k\geq 2$. Then:

  1. 1.

$L_{\\_}1\cup L_{\\_}2$ is a (repetition-free) $k$-PHRS language; 8cm (closure
under union)

  2. 2.

$L_{\\_}1L_{\\_}2$ is a (repetition-free) $k$-PHRS language; 8cm (closure
under concatenation)

  3. 3.

$L_{\\_}1^{+}$ is a (repetition-free) $k$-PHRS language. 8cm (closure under
Kleene plus)

###### Proof.

Combine Theorem 3.18 and Lemma 3.20. ∎

We now show closure under rational intersection, inspired by the proof of
Theorem V.1.7(iv) of [28]:

######  Theorem 3.22 (PHRS Closed Under Rational Intersection).

Let $L\subseteq A^{*}$ be a (repetition-free) $k$-PHRS language and
$K\subseteq B^{*}$ be a regular language, for any $k\geq 2$. Then $L\cap K$ is
a (repetition-free) $k$-PHRS language.

###### Proof.

There is a (repetition-free) $k$-PHR grammar
$\mathcal{G}=(\mathcal{C}=(\Sigma,\mathrm{type}),A,\mathcal{T}=\\{T_{\\_}1,\dots
T_{\\_}n\\},S)$ such that $\mathrm{L}(\mathcal{G})$ is a string graph language
and $\mathrm{STR}(\mathrm{L}(\mathcal{G}))=L\setminus\\{\epsilon\\}$. Without
loss of generality, we assume that $(\Sigma\setminus A)\cap B=\emptyset$.
There must also be a deterministic full FSA $\mathcal{M}=(Q,B,\delta,p,F)$
such that $\mathrm{L}(\mathcal{M})=K\setminus\\{\epsilon\\}$. We will now
construct a (repetition-free) $k$-PHR grammar with control
$\mathcal{G}^{\prime}=(\mathcal{C}^{\prime},A\cap
B,\mathcal{T}^{\prime},S,\mathcal{M}^{\prime})$ such that
$\mathrm{L}(\mathcal{G}^{\prime})$ is a string graph language and
$\mathrm{STR}(\mathrm{L}(\mathcal{G}^{\prime}))=(L\cap
K)\setminus\\{\epsilon\\}$, thus proving that $L\cap K$ is a (repetition-free)
$k$-PHRS language, using Theorem 3.10.

First, we define the signature $\mathcal{C}^{\prime}$. Let
$\Delta=(\bigcup_{\\_}{0\leq i\leq k}\\{\mathrm{type}^{-1}(\\{i\\})\times
Q^{i}\\})$, $\Sigma^{\prime}=\Delta\cup\\{S\\}\cup(A\cap B)$,
$\mathrm{type}^{\prime}((X,q_{\\_}1,\dots q_{\\_}i))=\mathrm{type}(X)$ for all
$(X,q_{\\_}1,\dots q_{\\_}i)\in\Delta$, $\mathrm{type}^{\prime}(S)=2$, and
$\mathrm{type}^{\prime}(X)=2$ for all $X\in A\cap B$.

In order to define $\mathcal{T}^{\prime}$ it will be useful to introduce the
intermediate notion of a hypergraph with node labels. In particular, we are
interested in labelling the nodes by states of $\mathcal{M}$. A node labelled
hypergraph over $(\mathcal{C},Q)$ is a pair $(H,l)$ where $H$ is a hypergraph
over $\mathcal{C}$ and $l$ is a function $V_{\\_}H\to Q$. Notice that any such
node labelled hypergraph can be encoded as a hypergraph over
$(\Delta,{\mathrm{type}^{\prime}\\!\\!\mid_{\scaleto{\Delta}{6pt}}})$: for
each $e\in E_{\\_}H$, the new hyperedge labelling function is defined by
sending $e$ to $(\mathrm{lab}_{\\_}H(e),q_{\\_}1,\dots,q_{\\_}i)$ where
$i=\mathrm{type}_{\\_}H(e)$ and $q_{\\_}j=l(\mathrm{att}_{\\_}H(e)(j))$ for
$1\leq j\leq i$. Call this injective encoding function $\mathrm{enc}$. Next,
given a type $t$ hypergraph $H$ over $\mathcal{C}$ and a sequence
$\sigma:\underline{t}\to Q$, define
$\mathrm{CHOICES}_{\\_}Q(H,\sigma)=\\{\mathrm{enc}((H,l))\mid l:V_{\\_}H\to
Q,l\circ\mathrm{ext}_{\\_}H=\sigma\\}$.

We now define
$\mathcal{T}^{\prime}=\\{T_{\\_}0^{\prime},T_{\\_}1^{\prime},\dots
T_{\\_}n^{\prime}\\}$ where:

  1. 1.

$T_{\\_}0^{\prime}=\mathcal{R}\oplus\\{((X,q_{\\_}1,q_{\\_}2),Y^{\bullet})\mid
X\in A\cap B,\delta(q_{\\_}1,X)=q_{\\_}2\\}$;

  2. 2.

$T_{\\_}i^{\prime}=\mathcal{R}\oplus(\bigcup_{\\_}{(L,R)\in
T_{\\_}i}\\{((L,\sigma(1),\dots,\sigma(t)),H)\mid
t=\mathrm{type}(L),\sigma:\underline{t}\to
Q,H\in\mathrm{CHOICES}_{\\_}Q(R,\sigma)\\}\cup\\{(S,(S,p,q)^{\bullet})\mid
q\in F\\})$, for $1\leq i\leq n$;

where $\mathcal{R}=\\{(X,X^{\bullet})\mid X\in\Sigma^{\prime}\\}$.

Finally, let $\mathcal{M}^{\prime}$ be an FSA defined by the regular
expression $\\{1,\dots,n\\}^{+}0$. Correctness follows from the fact that the
application of the final table $T_{\\_}0$ will produce a terminal string graph
$(x_{\\_}1x_{\\_}2\cdots x_{\\_}m)^{\bullet}$ if and only if the previous
hypergraph was a string graph of the form
$((x_{\\_}1,q_{\\_}1,q_{\\_}2)(x_{\\_}2,q_{\\_}2,q_{\\_}3)\cdots(x_{\\_}m,q_{\\_}m,q_{\\_}{m+1}))^{\bullet}$
and $\delta(q_{\\_}i,x_{\\_}i)=q_{\\_}{i+1}$ for $1\leq i\leq m$,
$q_{\\_}1=p$, and $q_{\\_}{m+1}\in F$. That is, we have traced out an
accepting path in the FSA $\mathcal{M}$, having simulated $\mathcal{G}$. ∎

Finally, we show closure under inverse homomorphisms, via the following
general result:

######  Lemma 3.23.

Let $\mathcal{F}$ be a class of string languages which is closed under
rational substitution and rational intersection. Let $L\subseteq A^{*}$ be an
$\mathcal{F}$ language and $\varphi:B^{*}\to A^{*}$ a homomorphism. Then
$\varphi^{-1}(L)$ is an $\mathcal{F}$ language too.

###### Proof.

Let $\mkern 1.5mu\overline{\mkern-1.5muB\mkern-1.5mu}\mkern 1.5mu$ be a copy
of $B$ such that $(A\cup B)\cap\mkern
1.5mu\overline{\mkern-1.5muB\mkern-1.5mu}\mkern 1.5mu=\emptyset$, and let
$\mkern 1.5mu\overline{\mkern-1.5mu\,\cdot\,\mkern-1.5mu}\mkern
1.5mu:B\to\mkern 1.5mu\overline{\mkern-1.5muB\mkern-1.5mu}\mkern 1.5mu$
identify each $b\in B$ with its copy $\mkern
1.5mu\overline{\mkern-1.5mub\mkern-1.5mu}\mkern 1.5mu\in\mkern
1.5mu\overline{\mkern-1.5muB\mkern-1.5mu}\mkern 1.5mu$. For each $a\in A$,
define the regular language $L_{\\_}a=\\{w_{\\_}1aw_{\\_}2\mid
w_{\\_}1,w_{\\_}2\in\mkern 1.5mu\overline{\mkern-1.5muB\mkern-1.5mu}\mkern
1.5mu^{*}\\}\subseteq(A\cup\mkern
1.5mu\overline{\mkern-1.5muB\mkern-1.5mu}\mkern 1.5mu)^{*}$ and the rational
substitution $h$ on $A$ by $a\mapsto L_{\\_}a$. Also define
$K=\bigcup_{\\_}{n\in\mathbb{N}}\\{\varphi(x_{\\_}1)\mkern
1.5mu\overline{\mkern-1.5mux_{\\_}1\mkern-1.5mu}\mkern
1.5mu\varphi(x_{\\_}2)\mkern
1.5mu\overline{\mkern-1.5mux_{\\_}2\mkern-1.5mu}\mkern
1.5mu\cdot\cdot\cdot\varphi(x_{\\_}n)\mkern
1.5mu\overline{\mkern-1.5mux_{\\_}n\mkern-1.5mu}\mkern 1.5mu\mid
x_{\\_}1,x_{\\_}2,\dots x_{\\_}n\in B\\}$ and the homomorphism
$\psi:(A\cup\mkern 1.5mu\overline{\mkern-1.5muB\mkern-1.5mu}\mkern
1.5mu)^{*}\to B^{*}$ by $\psi(a)=\epsilon$ for each $a\in A$ and $\psi(\mkern
1.5mu\overline{\mkern-1.5mub\mkern-1.5mu}\mkern 1.5mu)=b$ for each $b\in B$.

Notice $h(L)\cap K=\bigcup_{\\_}{n\in\mathbb{N}}\\{\varphi(x_{\\_}1)\mkern
1.5mu\overline{\mkern-1.5mux_{\\_}1\mkern-1.5mu}\mkern
1.5mu\varphi(x_{\\_}2)\mkern
1.5mu\overline{\mkern-1.5mux_{\\_}2\mkern-1.5mu}\mkern
1.5mu\cdot\cdot\cdot\varphi(x_{\\_}n)\mkern
1.5mu\overline{\mkern-1.5mux_{\\_}n\mkern-1.5mu}\mkern 1.5mu\mid
x_{\\_}1,\dots,x_{\\_}n\in B\text{ and
}\varphi(x_{\\_}1)\varphi(x_{\\_}2)\cdots\varphi(x_{\\_}n)\in L\\}$, so we
have $\varphi^{-1}(L)=\psi(h(L)\cap K)$. Now, $h(L)$ is an $\mathcal{F}$
language since $\mathcal{F}$ is closed under rational substitution, $h(L)\cap
K$ is an $\mathcal{F}$ language since $\mathcal{F}$ is closed under rational
intersection, and $\psi(h(L)\cap K)$ is an $\mathcal{F}$ language since
$\mathcal{F}$ is closed under homomorphisms (a special case of rational
substitution). Thus, $\varphi^{-1}(L)$ is an $\mathcal{F}$ language, as
required. ∎

######  Theorem 3.24 (PHRS Closed Under Inverse Homomorphisms).

For all $k\geq 2$, $\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{k}$ is
closed under inverse homomorphisms.

###### Proof.

The result follows from Theorems 3.18 and 3.22 and Lemma 3.23. ∎

###  3.5 Group Word Problem Closure Properties

Since the class of $k$-PHRS languages is a full AFL for any $k\geq 2$, it
satisfies the following important properties:

######  Theorem 3.25 (WP Independent Of Presentation [16]).

Let $\mathcal{F}$ be a class of string languages which is closed under inverse
homomorphisms, and let $\langle X\mid R\rangle$ be a presentation of a group
$G$ such that $\mathrm{WP}_{\\_}X(G)$ is an $\mathcal{F}$ language. Then all
presentations $\langle X^{\prime}\mid R^{\prime}\rangle$ of $G$ are such that
$\mathrm{WP}_{\\_}{X^{\prime}}(G)$ is an $\mathcal{F}$ language.

######  Theorem 3.26 (WP Subgroup and Supergroup Closure [12]).

Let $\mathcal{F}$ be a full AFL and $G$ be a group with word problem in
$\mathcal{F}$. Then every finitely generated subgroup and every finite index
supergroup of $G$ has word problem in $\mathcal{F}$.

In 2019, Kropholler and Spriano showed that a graph of groups with vertex
groups with MCF word problem and edge groups finite, yields a group with an
MCF word problem [21]. A special case of this construction is a free product
of groups. We now show that a free product of groups with (repetition-free)
PHRS word problems is a group with a (repetition-free) PHRS word problem. Our
strategy is entirely different to Kropholler and Spriano’s approach, which
relied on Denkinger’s automata characterisation of MCF languages (Theorem
2.4).

The following easy lemma, where presentations of groups are written as monoid
presentations, gives us a recursive description of the word problem of free
products, enabling us to prove Theorem 3.28.

######  Lemma 3.27.

Let $G_{\\_}1$, $G_{\\_}2$ be finitely generated groups over disjoint
alphabets $A_{\\_}1=\\{a_{\\_}1,\dots a_{\\_}n\\}$,
$A_{\\_}2=\\{b_{\\_}1,\dots b_{\\_}m\\}$, respectively. If $X=A_{\\_}1\cup
A_{\\_}2$ and $L_{\\_}i=\mathrm{WP}_{\\_}{A_{\\_}i}(G_{\\_}i)$ for $i=1,2$,
then $\mathrm{WP}_{\\_}{X}(G_{\\_}1*G_{\\_}2)$ is the smallest set $L$ such
that $\epsilon\in L$ and $\forall i\in\\{1,2\\},\forall w\in L_{\\_}i,\forall
u,v\in X^{*},uv\in L\Rightarrow uwv\in L$.

######  Theorem 3.28 (WP Free Product Closure).

Let $\mathcal{F}$ be a class of string languages containing all finite
languages, closed under union and concatenation, and closed under nested
iterated substitution. Then if $G_{\\_}1$, $G_{\\_}2$ are groups with
presentations admitting a $\mathcal{F}$ word problem, $G_{\\_}1*G_{\\_}2$ has
a presentation admitting a $\mathcal{F}$ word problem.

###### Proof.

Let $A_{\\_}1$, $A_{\\_}2$, $X$, $L_{\\_}1$, $L_{\\_}2$, $L$ be as in Lemma
3.27, then it is immediate that iterated application of the nested non-erasing
$\mathcal{F}$-substitution $h$ of strings on $A_{\\_}1\cup A_{\\_}2$, defined
by $h(a_{\\_}i)=\\{a_{\\_}i\\}\cup a_{\\_}iL_{\\_}1\cup L_{\\_}1a_{\\_}i$ and
$h(b_{\\_}j)=\\{b_{\\_}j\\}\cup b_{\\_}jL_{\\_}2\cup L_{\\_}2b_{\\_}j$ for all
$i\in\underline{n},j\in\underline{m}$, to $L$, gives us exactly
$\mathrm{WP}_{\\_}{X}(G_{\\_}1*G_{\\_}2)$. The result them follows from the
assumed closure properties. ∎

##  4 Conclusion and Future Work

We have shown some foundational properties of parallel hyperedge replacement
grammars, with a focus on string generational power, showing that the class of
parallel hyperedge replacement string languages is a substitution and iterated
substitution closed full AFL, containing all MCF and ET0L languages. Theorem
2.2 tells us that the string generational power of HR grammars is not
restricted by requiring grammars to be repetition-free. It remains future work
to determine if a similar result holds in the parallel replacement setting. If
it turns out that there is no such result, there is still a middle-ground
where one can obtain all of the closure properties we have shown, but without
allowing merging of nodes by derivations. Call the below equivalent classes
the repetition-free weak-coded $k$-PHRS languages
($\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}$):

  1. 1.

The class of string languages generated by repetition-free $k$-PHR grammars
under the image of some weak coding.

  2. 2.

The class of string languages generated by repetition-free $k$-PHR grammars
with a special type $2$ label empty, interpreted as the empty string by
$\mathrm{STR}$.

Using the results and proofs from Subsection 3.4, it is not too difficult to
see that
$\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}$
is a substitution and iterated substitution closed full AFL, and that
$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2^{\mathrm{rf}}=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2$,
due to the proof of Theorem 3.15. We conjecture this holds for all $k\geq 2$:

######  Conjecture 4.1 (PHR String Generational Power).

For all $k\geq 2$,
$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}^{\mathrm{rf}}_{\\_}k=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k$.

Figure 7 summarises the closure properties we know. It remains future work to
show that the class of PHRS languages is a strict subclass of the context-
sensitive languages. We conjecture this to be true, and we also conjecture
that only even increments in order increase string generative power. Figure 8
summarises both our known and conjectured string language hierarchies.

######  Conjecture 4.2 (CS Generalises PHRS).

$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}\subsetneq\mathcal{C}\mathcal{S}$.

######  Conjecture 4.3 (PHRS Grouping).

For all $k\geq 1$,
$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}$.

Because $\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}$ is closed under inverse
homomorphisms, we know that the property of having a PHRS word problem is
independent of the presentation. We have additionally shown that PHRS groups
are closed under free product. We also conjecture the following, which has a
wide-reaching corollary:

######  Conjecture 4.4 (PHRS WP Double Torus).

The fundamental group of the double torus admits a PHRS word problem which is
neither an MCF nor ET0L language.

######  Corollary 4.5.

If Conjecture 4.4 is true, then the word problem of any surface group is PHRS.

###### Proof.

By a _surface_ here, we mean a closed, connected, orientable, 2-manifold, and
by a _surface group_ , we mean the fundamental group of a surface. Any surface
always has a finite genus. The genus $0$ surface (the sphere) gives us the
trivial group, and $1$ (the torus), $\mathbb{Z}^{2}$ (see for example [22]).
We know both of these groups are regular, $2$-MCF [17], respectively, so
certainly PHRS (Theorem 3.17).

For higher genuses, it follows from the Fundamental Theorem of Covering Spaces
(Theorem 1.38 of [15]) that the fundamental group appears as a finitely
generated subgroup of the fundamental group of a genus $2$ surface such as a
double torus. Since $\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}$ is a full
AFL, if the double torus has fundamental group with PHRS word problem, then
all its finitely generated subgroups do too (Theorem 3.26). ∎

Highly related to the word problem is the consideration of sets of solutions
of more general equations over groups or other structures. It is a recent
result that solution sets (of fixed normal forms) of finite systems of
equations in hyperbolic groups are EDT0L languages [6]. We are yet to consider
deterministic parallel hyperedge replacement, but it may be possible to
establish that other classes of groups have solution sets that are
deterministic parallel hyperedge replacement string languages.

It remains future work to consider the effect of tables on generative power.
It is a long-standing result that ET0L grammars with only one table have less
generative power than those with two tables, and that allowing more than two
tables does not increase generative power any further [28]. It is likely that
a similar result holds for PHR and PHRS languages. Other more general future
work would include investigating both the tree and graph generational power of
PHR grammars, and investigating decidability and complexity results for basic
problems relating to PHR grammars. We do not know if the emptiness or
finiteness problems for PHR grammars are decidable, but we conjecture that
they are.

######  Conjecture 4.6 (Decidable PHR Emptiness).

The following problem is decidable:

######  Problem 1.

######  Conjecture 4.7 (Decidable PHR Finiteness).

The following problem is decidable:

######  Problem 2.

Operation/Class |  $\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}$ $=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k$ |  $\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}$ |  $\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k^{\mathrm{rf}}$ |  $\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}k$
---|---|---|---|---
Rational Operations | ✓ | ✓ | ✓ | ✓
Rational Intersection | ✓ | ✓ | ✓ | ✓
Inverse Homomorphisms | ✓ | ? | ✓ | ✓
Non-Erasing Homomorphisms | ✓ | ✓ | ✓ | ✓
Arbitrary Homomorphisms | ✓ | ? | ✓ | ✓
Non-Erasing Substitutions | ✓ | ✓ | ✓ | ✓
Arbitrary Substitutions | ✓ | ? | ✓ | ✓
Iterated Nested Non-Erasing Substitutions | ✓ | ✓ | ✓ | ✓
Iterated Nested Arbitrary Substitutions | ✓ | ? | ✓ | ✓
Iterated Non-Erasing Substitutions | ✗ | ✓ | ✓ | ✓
Iterated Arbitrary Substitutions | ✗ | ? | ✓ | ✓

Figure 7: Summary of formal language closure properties ($k\geq 2$)

$\mathcal{M}\mathcal{C}\mathcal{F}_{\\_}2=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}4^{\mathrm{rf}}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}5^{\mathrm{rf}}$$=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}4=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}5$$\mathcal{M}\mathcal{C}\mathcal{F}_{\\_}k=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}^{\mathrm{rf}}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}^{\mathrm{rf}}$$=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}$$\mathcal{M}\mathcal{C}\mathcal{F}_{\\_}{k+1}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+2}^{\mathrm{rf}}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+3}^{\mathrm{rf}}$$=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+2}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+3}$$\mathcal{M}\mathcal{C}\mathcal{F}=\mathcal{H}\mathcal{R}\mathcal{S}^{\mathrm{rf}}=\mathcal{H}\mathcal{R}\mathcal{S}$$\mathcal{C}\mathcal{F}=\mathcal{M}\mathcal{C}\mathcal{F}_{\\_}1=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2^{\mathrm{rf}}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}3^{\mathrm{rf}}$$=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}3$$\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2^{\mathrm{rf}}$$=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{3}^{\mathrm{rf}}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{4}^{\mathrm{rf}}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{5}^{\mathrm{rf}}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}^{\mathrm{rf}}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}^{\mathrm{rf}}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+2}^{\mathrm{rf}}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+3}^{\mathrm{rf}}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}^{\mathrm{rf}}$$\mathcal{C}\mathcal{S}$$\mathcal{R}\mathcal{E}\mathcal{C}$$\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{3}^{\mathrm{rf}}$$\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{4}^{\mathrm{rf}}$$\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{5}^{\mathrm{rf}}$$\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}^{\mathrm{rf}}$$\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}^{\mathrm{rf}}$$\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+2}^{\mathrm{rf}}$$\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+3}^{\mathrm{rf}}$$\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}^{\mathrm{rf}}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{3}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{4}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{5}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+2}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+3}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}$

(a) Proved string language hierarchy

$\mathcal{M}\mathcal{C}\mathcal{F}_{\\_}2=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}4^{\mathrm{rf}}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}5^{\mathrm{rf}}$$=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}4=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}5$$\mathcal{M}\mathcal{C}\mathcal{F}_{\\_}k=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}^{\mathrm{rf}}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}^{\mathrm{rf}}$$=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}$$\mathcal{M}\mathcal{C}\mathcal{F}_{\\_}{k+1}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+2}^{\mathrm{rf}}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+3}^{\mathrm{rf}}$$=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+2}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+3}$$\mathcal{M}\mathcal{C}\mathcal{F}=\mathcal{H}\mathcal{R}\mathcal{S}^{\mathrm{rf}}=\mathcal{H}\mathcal{R}\mathcal{S}$$\mathcal{C}\mathcal{F}=\mathcal{M}\mathcal{C}\mathcal{F}_{\\_}1=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2^{\mathrm{rf}}=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}3^{\mathrm{rf}}$$=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2=\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}3$$\mathcal{C}\mathcal{S}$$\mathcal{R}\mathcal{E}\mathcal{C}$$\mathcal{E}\mathcal{T}\mathcal{O}\mathcal{L}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}3^{\mathrm{rf}}=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2^{\mathrm{rf}}$$=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}3^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}2=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}3$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}4^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}5^{\mathrm{rf}}=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}4^{\mathrm{rf}}$$=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}5^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}4=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}5$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}^{\mathrm{rf}}=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}^{\mathrm{rf}}$$=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+1}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+2}^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+3}^{\mathrm{rf}}=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+2}^{\mathrm{rf}}$$=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+3}^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+2}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}_{\\_}{2k+3}$$\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}^{\mathrm{rf}}=\mathcal{W}\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}^{\mathrm{rf}}=\mathcal{P}\mathcal{H}\mathcal{R}\mathcal{S}$

(b) Conjectured string language hierarchy

Figure 8: Detailed formal language hierarchies ($k\geq 3$)

Acknowledgements. I should like to thank Detlef Plump for introducing me to
graph transformation and teaching me to write papers for this audience, my
supervisors Sarah Rees and Andrew Duncan for their guidance, Annegret Habel
and Meng-Che Ho for their helpful email discussions regarding hyperedge
replacement and surface groups, respectively, and Murray Elder for introducing
me to MCF languages. I am also grateful to the anonymous reviewers for their
comments, leading to a much-improved paper.

## References

  * [1]
  * [2] Alfred Aho (1968): _Indexed Grammars – An Extension of Context-Free Grammars_.  Journal of the ACM 15(4), pp. 647–671, 10.1145/321479.321488.
  * [3] Alfred Aho & Jeffrey Ullman (1972): _Translations on a Context Free Grammar_.  Information and Control 19(5), pp. 439–475, 10.1016/S0019-9958(71)90706-6.
  * [4] Anatoly Anisimov (1971): _Group languages_.  Cybernetics 7, pp. 594–601, 10.1007/BF01071030.
  * [5] Peter Asveld (1977): _Controlled iteration grammars and full hyper-AFL’s_.  Information and Control 34(3), pp. 248–269, 10.1016/S0019-9958(77)90308-4.
  * [6] Laura Ciobanu & Murray Elder (2019): _Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE_.  In: Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Leibniz International Proceedings in Informatics (LIPIcs) 132, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 110:1–110:15, 10.4230/LIPIcs.ICALP.2019.110.
  * [7] Laura Ciobanu, Murray Elder & Michal Ferov (2018): _Applications of L systems to group theory_.  International Journal of Algebra and Computation 28(2), pp. 309–329, 10.1142/S0218196718500145.
  * [8] Tobias Denkinger (2016): _An Automata Characterisation for Multiple Context-Free Languages_.  In: Proc. International Conference on Developments in Language Theory (DLT 2016), Lecture Notes in Computer Science 9840, Springer, pp. 138–150, 10.1007/978-3-662-53132-712.
  * [9] Frank Drewes, Hans-Jörg Kreowski & Annegret Habel (1997): _Hyperedge Replacement Graph Grammars_ , pp. 95–162.  World Scientific, 10.1142/97898123847200002.
  * [10] Andrzej Ehrenfeucht & Grzegorz Rozenberg (1977): _On some context-free languages that are not deterministic ET0L languages_.  R.A.I.R.O. Informatique théorique 11(4), pp. 273–291, 10.1051/ita/1977110402731.
  * [11] Joost Engelfriet & Linda Heyker (1991): _The string generating power of context-free hypergraph grammars_.  Journal of Computer and System Sciences 43(2), pp. 328–360, 10.1016/0022-0000(91)90018-Z.
  * [12] Robert Gilman, Robert Kropholler & Saul Schleimer (2018): _Groups whose word problems are not semilinear_.  Groups Complexity Cryptology 10(2), pp. 53–62, 10.1515/gcc-2018-0010.
  * [13] Robert Gilman & Michael Shapiro (1998): _On groups whose word problem is solved by a nested stack automaton_.  Available at https://arxiv.org/abs/math/9812028.
  * [14] Annegret Habel (1992): _Hyperedge Replacement: Grammars and Languages_.  Lecture Notes in Computer Science 643, Springer, 10.1007/BFb0013875.
  * [15] Allen Hatcher (2002): _Algebraic Topology_.  Cambridge University Press.
  * [16] Thomas Herbst & Richard Thomas (1993): _Group presentations, formal languages and characterizations of one-counter groups_.  Theoretical Computer Science 112(2), pp. 187–213, 10.1016/0304-3975(93)90018-O.
  * [17] Meng-Che Ho (2018): _The word problem of $\mathbb{Z}^{n}$ is a multiple context-free language_.  Groups Complexity Cryptology 10(1), pp. 9–15, 10.1515/gcc-2018-0003.
  * [18] John Hopcroft, Rajeev Motwani & Jeffrey Ullman (2006): _Introduction to Automata Theory, Languages, and Computation_ , 3rd ed. edition.  Addison-Wesley.
  * [19] Hans-Jörg Kreowski (1992): _Parallel Hyperedge Replacement_ , pp. 271–282.  Springer, 10.1007/978-3-642-58117-517.
  * [20] Hans-Jörg Kreowski (1993): _Five facets of hyperedge replacement beyond context-freeness_.  In: Proc. 9th International Conference on Fundamentals of Computation Theory (FCT 1993), Lecture Notes in Computer Science 710, Springer, pp. 69–86, 10.1007/3-540-57163-95.
  * [21] Robert Kropholler & Davide Spriano (2019): _Closure properties in the class of multiple context-free groups_.  Groups Complexity Cryptology 11(1), pp. 1–15, 10.1515/gcc-2019-2004.
  * [22] William Massey (1977): _Algebraic Topology: An Introduction_.  Graduate Texts in Mathematics 56, Springer.
  * [23] David Muller & Paul Schupp (1983): _Groups, the Theory of Ends, and Context-Free Languages_.  Journal of Computer and System Sciences 26(3), pp. 295–310, 10.1016/0022-0000(83)90003-X.
  * [24] Mogens Nielsen (1975): _EOL systems with control devices_.  Acta Informatica 4, pp. 373–386, 10.1007/BF00289618.
  * [25] Taishin Nishida & Shigeko Seki (2000): _Grouped partial ET0L systems and parallel multiple context-free grammars_.  Theoretical Computer Science 246(1–2), pp. 131–150, 10.1016/S0304-3975(99)00076-6.
  * [26] Pyotr Novikov (1955): _Über die algorithmische Unentscheidbarkeit des Wortproblems in der Gruppentheorie_.  Trudy Matematicheskogo Instituta imeni V.A. Steklova 44, pp. 1–143.
  * [27] Rohit Parikh (1966): _On Context-Free Languages_.  Journal of the ACM 13(4), pp. 570–581, 10.1145/321356.321364.
  * [28] Grzegorz Rozenberg & Arto Salomaa (1980): _The Mathematical Theory of L Systems_.  Pure and Applied Mathematics 90, Academic Press.
  * [29] Sylvain Salvati (2015): _MIX is a 2-MCFL and the word problem in $\mathbb{Z}^{2}$ is captured by the IO and the OI hierarchies_.  Journal of Computer and System Sciences 81(7), pp. 1252–1277, 10.1016/j.jcss.2015.03.004.
  * [30] Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii & Tadao Kasami (1991): _On multiple context-free grammars_.  Theoretical Computer Science 88(2), pp. 191–229, 10.1016/0304-3975(91)90374-B.
  * [31] Vijay Shanker, David Weir & Aravind Joshi (1987): _Characterizing structural descriptions produced by various grammatical formalisms_.  In: Proc. 25th Annual Meeting on Association for Computational Linguistics (ACL ’87), Association for Computational Linguistics, pp. 104–111, 10.3115/981175.981190.
  * [32] David Weir (1992): _Linear context-free rewriting systems and deterministic tree-walking transducers_.  In: Proc. 30th Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, pp. 136–143, 10.3115/981967.981985.