Parallel Hyperedge Replacement String Languages
Graham Campbell∗
School of Mathematics, Statistics and Physics, Newcastle University
Newcastle upon Tyne, United Kingdom
g.j.campbell2@newcastle.ac.uk

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

1

Introduction

In general, the word problem is the question that asks whenever two strings represent the same element
in some structure. In the case of groups, this is the equivalent to asking if a single string is equivalent
to the identity, since if u, v are strings, then they are equal in a group if and only if uv−1 is equal tothe identity in the group. Thus, given a group presentation hX | Ri for a group G, the word problem is
equivalent to the membership problem for the string language WPX (G) = {w ∈ (X ∪ X −1 )∗ | w =G 1G }.
A natural question to ask is how hard is the word problem, in general, and for specific familiesof groups. Unsurprisingly, both the universal word problem and the word problem are undecidable ingeneral, even for finite presentations [15]. It is elementary that a presentation defines a finite group if andonly if it admits a regular word problem [2], and defines a finitely generated virtually free group if andonly if it admits a deterministic context-free word problem if and only if it admits a context-free word
problem [13]. In 2015, a major breakthrough of Salvati was published, showing that the word problemof Z2 is a multiple context-free (MCF) language [19, 18], and in 2018, Ho extended this result showingthat all finitely generated virtually Abelian groups admit MCF word problems [10]. This is exciting
because the MCF languages are exactly the string languages of hyperedge replacement grammars, which
are strictly contained in the context-sensitive string languages [6, 20]. It remains an open problem as
to which other families of groups admit MCF word problems, however we do at least know that thefundamental group of a hyperbolic three-manifold does not admit a MCF word problem [7].
There are of course, lots of other well-behaved language classes sitting in between the context-freeand context-sensitive classes, such as the indexed languages [1] or the subclass of ET0L languages [17].
It is not known if there are any groups with indexed word problems other than the virtually free groups,
although it has been shown this is the case for a strict subclass of the indexed languages not contained in
ET0L [8]. In particular, we don’t know if any hyperbolic groups have ET0L word problems [4] (otherthan the virtually free groups), such as the fundamental group of the double torus. It has been conjectured
that all ET0L group languages are only admitted by virtually free groups. We show the (group) language
hierarchy below, where necessarily strict inclusion uses a solid line, GP denotes the class of all group
languages (the class of word problems of all finitely generated groups).
∗ Supported by a Doctoral Training Grant from the Engineering and Physical Sciences Research Council (EPSRC) Grant
No. (2281162) in the UK.

Preliminary Report. Final version to appear in:
TERMGRAPH 2020

c G. Campbell
This work is licensed under theCreative Commons Attribution License.

2

Parallel Hyperedge Replacement String Languages
CS ∩ GPCS

ID ∩ GPID
MCF ∩ GPMCF

ET OL ∩ GP

ET OL
CF

DCF ∩ GP = CF ∩ GP
DCF
RAT

RAT ∩ GP(a) String Language Hierarchy(b) Group Language Hierarchy

Figure 1: Known Formal Language Hierarchies
The aim of this paper is to lay the foundations for another language class, combining the ideas fromET0L and hyperedge replacement grammars to yield a genuinely new language class: the parallel hyperedge replacement string (PHRS) languages, strictly containing the MCF and ET0L languages. While
parallel hyperedge replacement has been considered before [9, 12], the work is not extensive and does
not consider rational control or string generational power. Ultimately, our hope is that we might, oneday, be able to place the hyperbolic groups within this class. Note that knowledge of (geometric) grouptheory is not required to read and understand this paper - it is purely motivational!
We summarise the string language hierarchy below, with what we know from results, previous andfrom this paper, and also how we conjecture the hierarchy collapses when we restrict to group languages.
REC ∩ GPREC

CS ∩ GP

CS
PHRS
MCF

ID

PHRS ∩ GP

ET OL

MCF ∩ GP

CF

3

?

?

DCF ∩ GP = CF ∩ GP = ET OL ∩ GP = ID ∩ GP
DCF
RAT

RAT ∩ GP(a) Proved String Language Hierarchy(b) Conjectured Group Language Hierarchy

Figure 2: New Formal Language Hierarchies

2

Preliminaries

This section is mostly based on the survey [5]. A signature is a pair C = (Σ, type) where Σ is some finite
alphabet (we only consider finite alphabets in this paper, but the definition works, in principle, without
this restriction), called the label set, and type : Σ → N is a typing function which assigns to each label an

G. Campbell

3arity called its type. For the rest of paper, we will assume some arbitrary but fixed signature C = (Σ, type).
We also denote by seq(X) (iseq(X)) all finite sequences (finite injective sequences) on a set X.
An n-hypergraph is a tuple H = (VH , EH , attH , labH , extH ) where: VH is a finite set of nodes; EH
is a finite set of hyperedges; attH : EH → seq(VH ) is the attachment function; labH : EH → Σ is thelabelling function; extH : iseq(VH ) are the external nodes; such that labelling is compatible with typing(type ◦ labH = |·| ◦ attH ) and n is the type of H, where in an abuse of notation, we write type(H) := |extH |.
We also define typeH : EH → N by typeH := type ◦ labH , and for all e ∈ EH , whenever m = typeH (e) wecall e an m-hyperedge, and call a hyperedge e ∈ EH proper whenever attH (e) is injective. The class of all
hypergraphs over C is denoted HC , and G, H ∈ HC are isomorphic (G ∼= H) if there is a pair of bijectivefunctions (gV : VG → VH , gE : EG → EH ) such that attH ◦gE = gV∗ ◦attG ; labH ◦gE = labG ; gV ◦extG = extH .
Given a string w ∈ Σ+ of length n, its string graph is w• = ({v0 , . . . , vn }, {e1 , . . . , en }), att, lab, v0 vn )such that att(ei ) = vi−1 vi and lab(ei ) = w(i) for all 1 ≤ i ≤ n. We call v0 , begin, and vn , end. We
denote the class of all string graphs over C by SC . We also use the superscript bullet to denote the“handle” of a label. If X ∈ Σ is of type n, then the handle of X is the hypergraph X • = ({v1 , . . . , vn }, {e},att, lab, v1 · · · vn ) such that att(e) = v1 · · · vn and lab(e) = X. Note that these two definitions coincide for a
type 2 label, considered either as a label or as a string of length 1, thus there can be no confusion.
Let H ∈ HC be a hypergraph and B ⊆ EH be a set of hyperedges. Then σ : B → HC is called a
replacement function if type ◦ σ = typeH |B . The replacement of B in H using σ is denoted by H[σ ], andis the hypergraph obtained from H by: removing B from EH ; disjointly adding the nodes and hyperedgesof σ (e), for each e ∈ B; identifying the i-th external node of σ (e) with the i-th attachment node of e, foreach e ∈ B and i ∈ typeH (e), where λ = {1, . . . , λ } for any λ ∈ N. The external nodes of H[σ ] remain
exactly those of H. All hyperedges keep their original attachments and labels.
If H ∈ HC , B ⊆ EH and σ : B → HC , then H[σ ] exists exactly when σ is a replacement function,and is unique up to isomorphism. Moreover, nodes of H are never deleted or merged. If H ∈ HC ,B = {e1 , . . . , en } ⊆ EH , σ : B → HC be a replacement function, and Ri = σ (ei ) for all i ∈ n. Then we
write H[e1 /R1 , . . . , en /Rn ] in place of H[σ ].
Let N ⊆ Σ be a set of non-terminals. A rule (or production) over N is a pair p = (L, R) with L ∈ N,
R ∈ HC , and type(L) = type(R). Given H ∈ HC and R a set of rules, if e ∈ EH and (labH (e), R) ∈ R, thenwe say that H directly derives H 0 ∼= H[e/R] (using R), and write H ⇒R H 0 . For a given e and choice of0rule, H is unique up to isomorphism. Clearly this is a binary relation on HC . We say H ∈ HC derives H 0
if there is a sequence H ⇒R H1 ⇒R · · · ⇒R Hk ∼= H 0 for some k ∈ N. We write H ⇒kR H 0 or H ⇒∗R H 0 .
A hyperedge replacement grammar of order k (k-HR grammar) is a system G = (C, N, S, R) where:
C = (Σ, type) is a signature; N ⊆ Σ is the set of non-terminal labels; S ∈ N is the start symbol; R isa finite set of rules over N; with max({type(R) | (L, R) ∈ R}) ≤ k. We call Σ \ N the terminal labels.
The language generated G is L(G) = {H ∈ HC | S• ⇒∗R H with lab−1/ ⊆ HC . L ⊆ HC is called
H (N) = 0}a hyperedge replacement language of order k (k-HR language) if there is a k-HR grammar such that
L(G) = L. The class of HR languages is the union of all k-HR languages for k ∈ N.
Theorem 2.1 (Context-Freeness Lemma [5]). Let R be a finite set of rules over N, and H ∈ HC , X ∈ N
and k ∈ N. Then there is a derivation X • ⇒k+1 H if and only if there is a rule (X, R) ∈ R and a mapping−1•k(e) ;
σ : lab−1∑e∈lab−1 (N) k(e) = k.
R (N) → HC with H = R[σ ] such that: ∀e ∈ labR (N), labR (e) ⇒R

Theorem 2.2 (Linear-Growth Theorem [5]). Given an infinite HR language L, there exists an infinite
sequence of hypergraphs in L, say H0 , H1 , H2 , . . . and constants c, d ∈ N with c + d ≥ 1, such that for alli ∈ N, |VHi+1 | = |VHi | + c and |EHi+1 | = |EHi | + d.
The partial function that takes a hypergraph, and if it is a string graph, computes the string it represents, is denoted by STR : HC * Σ∗ . Clearly this function is total on SC , and undefined elsewhere. A

4Parallel Hyperedge Replacement String Languages

language L ⊆ HC is said to be a string graph language if L ⊆ SC . Given a HR grammar G that generates
a string graph language, then we write STR(L(G)) for the actual string language it generates. Without
loss of generality, we can assume all terminal labels are of type 2. A string language L ⊆ A∗ is called a
hyperedge replacement string language of order k (k-HRS language) if there is a signature C = (Σ, type)and a grammar k-HR grammar G over C such that: A ⊆ Σ and ∀x ∈ A, type(x) = 2; G generates a string
graph language; STR(L(G)) = L \ {ε}. The class of HRS languages is the union of all k-HRS languages
for k ∈ N. As we remarked in the introduction, these are exactly the multiple context-free languages:
Theorem 2.3 (String Generative Power [6, 20]). For all k ≥ 1, HRS2k = HRS2k+1 = MCFk .

3

New Results

We start by introducing a parallel version of direct derivations and the notion of a table, borrowed fromso-called T0L systems. We then define parallel hyperedge replacement grammars.
Definition 3.1 (Parallel Direct Derivation). Let H ∈ HC with EH = {e1 , . . . en }, and R be a set of rules. If
for each ei ∈ EH , there is an Ri ∈ HC such that (labH (ei ), Ri ) ∈ R, then we say that H parallelly directly
derives H 0 ∼= H[e1 /R1 , . . . , en /Rn ] (using R), and write H VR H 0 .
Definition 3.2 (Parallel Derivation). Let H ∈ HC , S = {Ri | i ∈ I} be a finite set of rule sets indexed byI, and M an FSA over I. Then H (M-)parallelly derives H 0 (using S) if there is a derivation sequence:∆ : H VRi1 H1 VRi2 · · · VRik Hk ∼= H0
i1 i2 ···ik0for some k ∈ N such that i1 i2 · · · ik ∈ L(M). We write H VM
H 0 , or H VkS H 0 .
S H , H VS

Definition 3.3 (Table). A table T is a finite set of rules over Σ such that for each L ∈ Σ, there is at least
one R ∈ HC such that (L, R) ∈ T .
Compared to hyperedge replacement grammars, rather than having a set of non-terminals, and only
replacing non-terinally labelled hyperedges, we allow all hyperedges to be replaced, and have a special
set of terminal symbols to allow us to define when it is that a hypergraph is terminally labelled. In fact,
the definition of a table ensures that progress can always be made, and each derivation step necessarily
replaces all the hyperedges, though not necessarily with something different.
Definition 3.4 (PHR Grammar). A parallel hyperedge replacement grammar of order k (k-PHR grammar) is a system G = (C, A, S, T , M) where C = (Σ, type) is a signature; A ⊆ Σ is the set of terminal labels;
S ∈ Σ \ A is the start symbol; T = {Ti | i ∈ I} is a finite set of tables indexed by I; M = (Q, I, δ , i, F) isS
an FSA over I; with max({type(R) | (L, R) ∈ Ti ∈T Ti }) ≤ k. We call Σ \ A the non-terminal labels. The−1language generated by G is L(G) = {H ∈ HC | S• VM
T H with labH (A) = EH } ⊆ HC . L ⊆ HC is calleda parallel hyperedge replacement language of order k (k-PHR language) if there is a k-PHR grammar G
such that L(G) = L. The class of PHR languages is the union of all k-PHR languages for k ∈ N.
Proposition 3.5. The PHR languages are closed under hypergraph isomorphism and are homogeneous.
Proof. By induction on the underlying sequential derivation length, where each parallel derivation canbe broken down into a sequence of direct derivations.
The inclusion of rational control, originally considered for ET0L [3], is a convenience to aid withthe specification of human understandable grammars and the process of combining grammars. On thesurface, one might worry this adds more generative power, making such systems more powerful than thatgiven by Habel [9], but actually the inclusion of rational control does not increase generational power.

G. Campbell

5Definition 3.6 (PHR Grammar Without Control). A k-PHR grammar without control is a tuple G =(C, A, S, T ) such that (C, A, S, T , M) is a k-PHR grammar where M is an FSA which accepts everything.
Its generated language is defined in the obvious way.
Lemma 3.7 (Control Removal). Given a k-PHR grammar G, one can effectively construct a k-PHR
grammar G 0 without control such that L(G) = L(G 0 ).
Proof. Let G = (C, A, S, T , M) and w.l.o.g. suppose that C = (Σ, type), T = {T1 , . . . Tn }, and M =(Q, n, δ , i, F) be deterministic and full with trap state t (see, for example [11]). We make |Q| disjoint
copies of Σ, Σq for each q ∈ Q. Let liftq : Σ → Σq be defined in the obvious way, for each q ∈ Q, and letSΣ = q∈Q Σq . We now construct G 0 = (C 0 , A, S0 , T 0 ):1. C 0 = (Σ0 , type0 ) with Σ0 = {S0 } ∪ Σ ∪ Σ, type0 |{S0 } = (S0 7→ type(S)), ∀q ∈ Q, type0 |Σq = type ◦ lift−1q ,and type0 |Σ = type;
2. S0 = lifti (S);
3. T 0 = {Ti0 | i ∈ (n × Q) ∪ {END}} where:0(a) ∀i ∈ n, q ∈ Q, T(i,q)= R ⊕ {(liftq (L), liftδ (q,i) (R)) | (L, R) ∈ Ti }0(b) TEND = R ⊕ ({(lift f (X), X) | f ∈ F, X ∈ Σ} ∪ {(liftq (X), liftt (X)) | q ∈ Q \ F, X ∈ Σ});where R = {(X, X • ) | X ∈ Σ0 } and ⊕ denotes relational override.
First, we show L(G) ⊆ L(G 0 ). By definition, G ∈ L(G) if and only if it is terminally labelled andthere is a derivation ∆ : S• ViT1 G1 ViT2 · · · ViTl G for some l ∈ N such that i1 i2 · · · il ∈ L(M). Notice how
the FSA M starts in the initial state i and then after reading i1 advances to some state, let’s call it qi1 ,and then after reading i2 ..., and then after reading il advances to some state, let’s call it qil . Now, it must
(i1 ,qi1 )be the case that qil ∈ F. Our construction of G 0 means we can simulate the derivation ∆0 : S0• VT 0
(i2 ,qi )(il ,qi )liftqi1 (G1 ) VT 0 2 · · · VT 0 l liftqil (G) VENDT 0 G, as required.
0
Finally, to see L(G ) ⊆ L(G), we argue that every derivation in G 0 from S0• to a terminally labelled
hypergraph can be transformed into a derivation of the above form, and then we can simply reverse oursimulation to give us the result.
0So, suppose we have a derivation in G 0 from S0• of length l. If step i ∈ l is an application of T(i,q)
0that replaces all edges by themselves, then that step can be deleted. If it is an application of TEND
then
it follows that all subsequent steps do nothing to the resultant graph. So, we can assume w.l.o.g. that0
any such derivation is a (possibly empty) sequence of direct derivations using a table T(i,q)
possibly0
followed by a direct derivation using the table TEND . Now, any derivation sequence that does not end
0with an application of TEND
necessarily must have derived a non-terminally labelled hypergraph, so we
can discount such derivation sequences. Next, due to the construction of our tables, any of the prescribedderivation sequences we are left with are exactly of the form from the forward direction of the proof(formally, by induction on derivation length), so have a corresponding derivation in G from S• .
Our next theorem confirms that PHR languages strictly contain the HR languages, as expected. We
note that our statement is actually stronger than Theorem 3.3 of Habel’s book [9], which sketches a proof
for only k ≥ 2. First, we provide an intermediate result (which is used both now, and later on):n

Proposition 3.8. L = {a2 | n ∈ N} is an ET0L language but not MCF. Moreover, it is not semilinear.
Proof. It is easy to see that G = ({a}, {a}, a, {{(a, aa)}}) is an ET0L grammar with L(G) = L. Recall
that a language is semilinear if and only if it is letter-equivalent to a regular language [16]. Since L is alanguage 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.

6

Parallel Hyperedge Replacement String Languages

Theorem 3.9 (PHR Generalises HR). For k ≥ 0, HRk ( PHRk .
Proof. Suppose C = (Σ, type) and G = (C, N, S, R) is a k-HR grammar with R = {r1 , . . . , rn }. Then weconstruct a k-PHR grammar G 0 = (C, A, S, T ) with A = Σ \ N and T = {T1 } where T1 = R ∪ {(X, X • ) |X ∈ Σ}. Clearly every parallel direct derivation with start hypergraph G can be decomposed into at most|EG | direct derivations where if an edge is replaced by itself, we omit it, and if a genuine replacementfrom R occurs, we use that. So, by induction on derivation length, we see that every parallel derivationin G 0 can actually be written as a derivation in G. Similarly, every direct derivation in G can be lifted to aparallel derivation in G 0 by replacing all but one edge by itself. So, by induction on derivation length, we
see that every derivation in G can be written as a parallel derivation in G 0 . Thus, together with the factthat the terminal symbols and start symbol coincide, we have that L(G) = L(G 0 ).
n
To see strictness, we are inspired by the fact that the string language {a2 | n ∈ N} is ET0L but not
MCF (Proposition 3.8). We will show there is a 0-PHR language that is not k-HR for any k ∈ N. Let
G = (C, A, S, T ) be the 0-PHR grammar with C = ({}, {(, 0)}), A = {}, S = , and T = {T1 }where T1 = {(, • t • )} (t denotes disjoint union of hypergraphs). Clearly L(G) is the language ofhypergraphs over C with 2n hyperedges. By Theorem 2.2, L(G) is not a HR language, as required.
Corollary 3.10. PHR languages need not have only linear growth, in the sense of Theorem 2.2.
We now turn our attention to string languages. We believe our definition of parallel hyperedge
replacement string languages is a genuinely new class of languages containing both the multiple contextfree languages and the ET0L languages. It is not simply equal to the (parallel) multiple context-freelanguages because these are known to be incomparable with ET0L [14]. Recall that the hyperedge replacement string languages are exactly the multiple context-free languages. We will confirm that parallel
hyperedge replacement string languages contain all of these and also all of the ET0L languages.
Definition 3.11 (Generated String Language). Given a PHR grammar G that generates a string graphlanguage, then we write STR(L(G)) for the actual string language it generates.
Proposition 3.12. Given a PHR grammar G = (C, A, S, T ) that generates a string graph language. w.l.o.g.
we can assume all terminals are of type 2. Moreover, if the generated language is non-empty, then thestart label S must be of type 2. In any case we can assume this w.l.o.g..
Proof. Any symbol labelling an edge of a string graph necessarily has type 2. Any terminally labelledstring graph has only terminal symbols labelling its edges. Thus only the type 2 terminal symbols areused to label the terminally labelled string graphs. We can safely delete the other symbols from theterminal set A. For the next part, using the fact that the generated language is non-empty, there is a
derivation sequence from S• to some string graph G. Since G is of type 2, it follows by induction onderivation length (as in the proof of Proposition 3.5) that S• is of type 2, thus S is of type 2. Finally, todeal with the w.l.o.g. statement, if the generated language is empty, then we can just have no tables andchoose S to be a type 2 symbol.
Definition 3.13 (PHR String Language). A string language L ⊆ A∗ is called a parallel hyperedge replacement string language of order k (k-PHRS language) if there is a signature C = (Σ, type) and a grammar
k-PHR grammar G over C such that: A ⊆ Σ and ∀x ∈ A, type(x) = 2; G generates a string graph language;
STR(L(G)) = L \ {ε}. The class of PHRS languages is the union of all k-PHR languages for k ∈ N.
Proposition 3.14. HRS0 = HRS1 = PHRS0 = PHRS1 = {0,/ {ε}}.
Proposition 3.15. Given a k-PHR grammar G, one can effectively construct a k-PHR grammar G 0 suchthat: all terminals and the start label S are of type 2; and all hyperedges in rules are proper; L(G) = L(G 0 ).

G. Campbell

7

Definition 3.16 (Useless Symbols). Given a PHR grammar G over C = (Σ, type). Call a symbol X ∈ Σuseful if it occurs as a label of some hypergraph in a derivation from the start hypergraph to any terminallylabelled hypergraph.
The following characterisation follows from Theorem 2.1 with not much work:
Proposition 3.17. Given a PHR grammar G = ((Σ, type), A, S, T ). A symbol X ∈ Σ is useful if and only
if it is both generating (∃n ∈ N, ∃G ∈ HC , X • Vn G and labG (EG ) ⊆ A) and reachable (∃n ∈ N, ∃G ∈HC , S• Vn G and X ∈ labG (EG )).
Moreover, we can iteratively compute the useless symbols in the usual way for context-free grammars(see, for example, Section 7.1 of [11]). Note also how we used the form of grammars without control inthat result - it is much more fiddly to define if have to handle control within the derivations.
Proposition 3.18. Given a k-PHR grammar G, one can effectively construct a k-PHR grammar G 0 suchthat there are no useless symbols and L(G) = L(G 0 ).
Next, we have a result about ET0L grammars which we will also need to show Lemma 3.20:
Proposition 3.19. Given an ET0L grammar G, one can effectively construct an ET0L grammar G 0 ) suchthat all rules necessarily have non-empty RHSs and L(G) \ {ε} = L(G 0 ).
Proof. This is due to Theorem 1.6 of Part V of Rozenberg and Salomaa [17] where they show that every
ET0L grammar has an equivalent EPT0L grammar, up to treatment of the empty string.
Lemma 3.20 (PHRS Generalises ET0L). ET OL = PHRS2 and for k ≥ 4, ET OL ( PHRSk .
Proof. First we show ET OL ⊆ PHRSk for all k ≥ 2. Suppose L is an ET0L language, then by Proposition 3.19 there exists an ET0L grammar G = (V, A, S, {Ti | i ∈ I}) such that no rule contains the empty
string and L \ {ε} = L(G). It follows that every rule can be encoded as a hyperedge replacement ruleover C 0 = (V,V × {2}) giving us a 2-PHR grammar G 0 = (C 0 , A, S, {{(L, R• ) | (L, R) ∈ Ti } | i ∈ I}) with
L(G = STR(L(G 0 )).
Next, we show that PHRS2 ⊆ ET OL. Suppose L is a 2-PHRS language, then there is a 2-PHR
grammar G = (C, A, S, {Ti | i ∈ I}) generating a string graph language such that L \ {ε} = STR(L(G)).
Due to Propositions 3.15 and 3.18, we can assume all the symbols are of type exactly 2, all hyperedges
occuring in the RHSs of rules are proper, and that there are no useless symbols in the signature. By
induction on derivation length, it is then obvious that any derivation that ends with a string graph mustbe such that all sub-derivations derive only string graphs. In particular, this means all rules have string
graphs as their RHSs. Every such grammar can be converted into an ET0L grammar.
Finally, strictness follows from Theorems 2.3 and 3.9, and the proof of Theorem 8 of [14].
Corollary 3.21. There are 2-PHRS languages that are not semilinear.
Proof. Lemma 3.20 gives us a 2-PHRS language which is not semilinear by Proposition 3.8.
Lemma 3.22 (PHRS Generalises MCF). For k ≥ 2, HRSk ( PHRSk .
Proof. This follows from Theorem 2.3, and Theorem 3.9 and its proof. We get strictness from Proposition 3.8 together with Lemma 3.20.
Conjecture 3.23 (CS Generalises PHRS). PHRS ( CS.
We have shown (not included in this paper, using Lemma 3.7) that we have ε-free substitution closure. If we can show full substitution closure and closure under rational intersection, then we have:
Conjecture 3.24 (Substitution-Closed Full AFL). For k ≥ 2, PHRSk and PHRS are substitutionclosed full abstract families of languages.

8

Parallel Hyperedge Replacement String Languages
The following corollary and its contrapositive, to the above conjecture, are extremely important:Corollary 3.25. For k ≥ 2, PHRSk and PHRS are closed under inverse homomorphisms. Moreover,
if a group has a PHRS word problem for some given presentation, then all presentations necessarily do.
Our final conjecture is wide reaching due to its corollary (assuming Conjecture 3.24 is true):
Conjecture 3.26 (WP Double Torus). The fundamental group of the double torus admits a PHRS word
problem which is neither a MCF nor ET0L language.
Corollary 3.27. The word problem of any surface group is a PHRS language.

References[1] Alfred Aho (1968): Indexed Grammars – An Extension of Context-Free Grammars. J. ACM 15(4), pp.
647–671, doi:10.1145/321479.321488.
[2] Anatoly Anisimov (1971): Group Languages. Kibernetika 4, pp. 18–24.
[3] Peter Asveld (1977): Controlled iteration grammars and full hyper-AFL’s. Information and Control 34(3),pp. 248–269, doi:10.1016/S0019-9958(77)90308-4.
[4] 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, doi:10.1142/S0218196718500145.
[5] Frank Drewes, Hans-Jörg Kreowski & Annegret Habel (1997): Hyperedge Replacement Graph Grammars,
pp. 95–162. World Scientific, doi:10.1142/9789812384720 0002.
[6] 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, doi:10.1016/0022-0000(91)90018-Z.
[7] Robert Gilman, Robert Kropholler & Saul Schleimer (2018): Groups whose word problems are not semilinear. Groups Complexity Cryptology 10(2), pp. 53–62, doi:10.1515/gcc-2018-0010.
[8] Robert Gilman & Michael Shapiro (1998): On groups whose word problem is solved by a nested stackautomaton. Available at https://arxiv.org/abs/math/9812028.
[9] Annegret Habel (1992): Hyperedge Replacement: Grammars and Languages. Lecture Notes in Computer
Science 643, Springer, doi:10.1007/BFb0013875.
[10] Meng-Che Ho (2018): The word problem of Zn is a multiple context-free language. Groups Complexity
Cryptology 10(1), pp. 9–15, doi:10.1515/gcc-2018-0003.
[11] John Hopcroft, Rajeev Motwani & Jeffrey Ullman (2006): Introduction to Automata Theory, Languages, andComputation, 3rd ed. edition. Addison-Wesley.
[12] Hans-Jörg Kreowski (1993): Five facets of hyperedge replacement beyond context-freeness. In Zoltán Ésik,
editor: Proc. 9th International Conference on Fundamentals of Computation Theory (FCT 1993), Lecture
Notes in Computer Science 710, Springer, pp. 69–86, doi:10.1007/3-540-57163-9 5.
[13] David Muller & Paul Schupp (1983): Groups, the Theory of Ends, and Context-Free Languages. Journal ofComputer and System Sciences 26(3), pp. 295–310, doi:10.1016/0022-0000(83)90003-X.
[14] Taishin Nishida & Shigeko Seki (2000): Grouped partial ET0L systems and parallel multiple context-freegrammars. Theoretical Computer Science 246(1–2), pp. 131–150, doi:10.1016/S0304-3975(99)00076-6.
[15] Pyotr Novikov (1955): Über die algorithmische Unentscheidbarkeit des Wortproblems in der Gruppentheorie. Trudy Matematicheskogo Instituta imeni V.A. Steklova 44, pp. 1–143.
[16] Rohit Parikh (1966): On Context-Free Languages. J. ACM 13(4), pp. 570–581, doi:10.1145/321356.321364.
[17] Grzegorz Rozenberg & Arto Salomaa (1980): The Mathematical Theory of L Systems. Pure and Applied
Mathematics 90, Academic Press.
[18] Sylvain Salvati (2015): MIX is a 2-MCFL and the word problem in Z2 is captured by the IO and the OI hierarchies. Journal of Computer and System Sciences 81(7), pp. 1252–1277, doi:10.1016/j.jcss.2015.03.004.
[19] Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii & Tadao Kasami (1991): On multiple context-free grammars. Theoretical Computer Science 88(2), pp. 191–229, doi:10.1016/0304-3975(91)90374-B.
[20] David Weir (1992): Linear context-free rewriting systems and deterministic tree-walking transducers. In:
Proc. 30th Annual Meeting of the Assoc. for Comput. Linguist., pp. 136–143, doi:10.3115/981967.981985.