Generation and Polynomial Parsing of Graph Languages with Non-Structural Reentrancies

Formal graph languages are commonly used to represent the semantics of natural and artificial languages. They are exceptionally versatile, lend themselves to human interpretation (in contrast to, for example, vector-based semantic representations), and have a comprehensive mathematical theory. Recent applications are the abstract meaning representations (AMRs) (Langkilde and Knight 1998; Banarescu et al. 2013) that capture the semantics of natural language sentences, and the work of Allamanis, Brockschmidt, and Khademi (2018), who use graphs to represent both the syntactic and semantic structure of source code. In these cases, it is common to represent objects as nodes, and relations as directed edges. Probabilities and other weights are sometimes added to reflect quantitative aspects such as likelihoods and uncertainties.

In this work, we propose the graph extension grammar for modeling languages of graph-based semantic representations. We formalize these grammars in a tree-based fashion in the sense of Drewes (2006). Thus, a grammar consists of a graph algebra $A$ and a tree grammar g. The trees generated by g are well-formed expressions over the operations of $A$⁠. Each generated tree thus evaluates into a graph, meaning that the tree language generated by g evaluates to a graph language. If we are careful about how we construct and combine g and $A$⁠, we can make parsing efficient. In other words, given a graph G, we can find a tree in the language of g that evaluates to G under $A$—or decide that no such tree exists, meaning that G is not in the graph language specified by g and $A$—in polynomial time. The main contribution of this work is the design of the algebra.

As a guiding example, we take the aforementioned AMR. (Note that since this article focuses on parsing in terms of membership problem solving, we do not go into the extensive string-to-AMR parsing literature.) AMR is characterized by its graphs being directed, acyclic, and having unbounded node degree. The concept was first introduced by Langkilde and Knight (1998) based on a semantic abstraction language by Kasper (1989). The notion was refined and popularized by Banarescu et al. (2013) and instantiated for a limited domain by Braune, Bauer, and Knight (2014). To ground AMR in formal language theory, Chiang et al. (2018) analyze the AMR corpus of Banarescu et al. (2013). They note that even though the node degree is generally low in practice, this is not always the case, which speaks in favor of models that allow an unbounded node degree. Regarding the treewidth of the graphs in the corpus, they find that it never exceeds 4 and conclude that an algorithm can depend exponentially on this parameter and still be feasible in practice.

In the context of semantic graphs, it is common to talk about reentrancies. Figure 1 illustrates this concept with a pair of AMR graphs, both of which require node sharing, or reentrant edges, to express the correct semantics. We propose to distinguish between two types of reentrancies: In the first graph, the reentrancy is structural, meaning that the boy must be the agent of whatever he is trying, so the “arg0” edge can only point to him. In the second graph, the reentrancy is non-structural in the sense that although in this particular case the girl believes herself, there is nothing to prevent her from believing someone else, or that someone else believes her. In general, we speak of (1) structural reentrancies when they are syntactically governed, for example, by control or coordination, and of (2) non-structural reentrancies when they can in principle refer to any antecedent, in some sense disregarding the structure of the graph in favor of the roles of the concepts. Structural reentrancy can, for example, also take the form of subject control as in “They persuaded him to talk to her”, where the person who talks and the person who was persuaded must be one and the same. In contrast, “[…], but she liked them” is an example of (2) since the antecedent of “them” may be picked from anywhere in “[…]” for the semantic representation to be valid.

A second important characteristic of AMR and other notions of semantic graphs in natural language processing is that certain types of edges, like those in Figure 1, point to arguments of which there should be at most one. For example, the concept “try” in Figure 1 must only have one outgoing “arg0” edge. Other edges, of types not present in Figure 1, can for example represent modifiers, such as believing strongly and with a passion. Outgoing edges of these types are usually not limited in number.

It is known that contextual hyperedge replacement grammars (CHRGs), an extension of the well-known context-free hyperedge replacement grammars (HRGs), can model both structural and non-structural reentrancies (Drewes and Jonsson 2017). To achieve this, contextual hyperedge replacement rules may contain so-called context nodes which, during the application of a rule, are identified with any appropriately labeled node of the graph to which the rule is applied. In particular, this allows for the generation of non-structural reentrancies, using rules that contain edges pointing to context nodes. Despite this added generative power compared to HRGs, previous research on CHRGs has resulted in a pumping lemma (Berglund 2019) for the generated graph languages and a parser generator (Drewes, Hoffmann, and Minas 2017, 2021, 2022) that, for a certain subclass of CHRGs, yields a parser that runs in quadratic (and in the common case, linear) time in the size of its input graph.¹ However, similarly to LL- and LR-parsers for ordinary context-free languages, and in contrast to our algorithm, the parser generator may discover parsing conflicts. In this case it is unable to construct a parser. Compared to the string case, the possible reasons for conflicts are much subtler, which makes grammar construction a complex and error-prone manual endeavor.

For this reason, we are now proposing graph extension grammars, a type of graph grammar that makes use of the idea of context nodes in a different way. It enables polynomial parsing based on an entirely syntactic condition on the rules (our main result Theorem 5) while retaining the ability to specify graph languages with reentrancies of both type (1) and (2). One key property of these grammars that allows for polynomial parsing is that, intuitively, nodes are provided with all of their outgoing edges the moment they are created. Using ordinary contextual hyperedge replacement, this would thus result in graph languages of bounded out-degree, the bound being given by the maximal number of outgoing edges of nodes in the right-hand sides of productions. To generate semantic graphs in which a concept can have an arbitrary number of dependents, we use a technique from Drewes et al. (2010) known as cloning. Here, tree-based graph generation is helpful because it allows us to incorporate both contextuality and cloning in a natural way without sacrificing efficient parsability. While tree-based hyperedge replacement grammars are well-known to be equivalent to ordinary ones (see below), the tree-based formulation does make a difference in the contextual case as it avoids the problem of cyclic dependencies that has not yet been fully characterized and can make parsing intractable (Drewes, Hoffmann, and Minas 2019).

The creation of reentrant edges via context nodes requires a control mechanism that ensures that edges are placed in a meaningful way. One must, for example, make certain that co-references refer to entities of the correct type and plurality. For such conditions, we use monadic second-order (mso) logic since it has many well-known ties to the theory of hyperedge replacement. In particular, the theorem commonly known as Courcelle’s theorem (see, e.g., Courcelle and Engelfriet 2012) states that mso formulas can be evaluated in linear time on graphs of bounded treewidth. The theorem is thus applicable to graphs generated by HRGs, because they generate graph languages of bounded treewidth. Unfortunately, the addition of non-structural reentrancies destroys this property and can cause a generated graph to have a treewidth proportional to the size of the graph. Despite this, we show in our main result that, if the mso formulas involved are local in a sense that restricts their ability to make general statements about the structure of the graph, then Courcelle’s theorem can be exploited to solve the membership problem in polynomial time. We also show that the membership problem is NP-complete if no restriction is imposed on the formulas.

We first prove our main result for graph extension grammars that are edge agnostic, meaning that their mso formulas are not allowed to make use of the edge predicate. Since this is a rather severe limitation that does not allow the placement of reentrant edges to be controlled by structural conditions at all, we show afterwards how it can be relaxed. We do so by allowing the logic to make use of predicates which, for a given node, state that this node belongs to a part of the graph having a certain form. The resulting local graph extension grammars are much more general than the edge-agnostic ones, but they still allow for polynomial parsing. We note here that, in fact, our algorithm works correctly even without any such restriction, the only downside being a lack of efficiency. With this in mind, it may be worth noting that neither edge agnosticism nor locality are needed to be able to apply Courcelle’s theorem if we are only interested in parsing graphs of bounded treewidth. For AMR, by checking the AMR bank, Chiang et al. (2018) observed that, although there is no theoretical upper limit on the treewidth of AMR graphs, in practice AMR graphs of treewidth larger than 5 are extremely rare. Hence, if one is willing to place such a bound on the treewidth of acceptable AMR graphs, then Courcelle’s theorem and thus our result can be used even without the locality assumption.

Regardless, it is our belief that locality, from a practical point of view, is not a particularly severe restriction. In fact, even edge agnosticism may be tolerable in many practical cases. This is because, as long as we are interested in the generation of AMR-like structures, the primary use of context nodes is to be able to describe reentrancies caused by language elements such as pronouns. Simplifying the situation only a little, one may say that a pronoun may refer to any suitable antecedent in the sentence, wherever and in whichever role it occurs. This is essentially saying that their placement is edge agnostic even from a linguistic point of view. For example, if the pronoun “he” occurs in a sentence (or its AMR graph) that also has an occurrence of “Bob” then the former may refer to the latter, regardless of which other edges point to Bob. The only thing that (usually) matters is whether the label “Bob” refers to a person that uses the personal pronoun “he”.

Tree-based generation dates back to the seminal article by Mezei and Wright (1967), which generalizes context-free languages to languages over arbitrary domains, by evaluating the trees of a regular tree language with respect to an algebra.² Operations on graphs were used in this way for the first time by Bauderon and Courcelle (1987). See the textbook by Courcelle and Engelfriet (2012) for the eventual culmination of this line of work. Graph operations similar to those used here (though without the contextual extension) appeared first in Courcelle’s work on the mso logic of graphs (Courcelle 1991, Definition 1.7). Essentially, if the right-hand side of a production contains k nonterminal hyperedges, it is viewed as an operation that takes k hypergraphs as arguments (corresponding to the hypergraphs generated by the k subderivations) and returns the hypergraph obtained by replacing the nonterminals in the right-hand side by those k argument hypergraphs. By context-freeness, evaluating the tree language that corresponds to the set of derivation trees of a grammar of such productions (which is a regular tree language) yields the same set of hypergraphs as is generated by the grammar itself.

This two-step approach is somewhat similar to that of lexical-functional grammar (LFG) by Kaplan and Bresnan (1982): In LFG, a c-structure containing syntactical information about a sentence and an f-structure that provides its semantic information are combined to create a representation for a language user’s syntactic knowledge. The c-structure is comparable to a derivation tree, while the semantic f-structure that applies semantic knowledge on top of that can be compared to the algebraic operations on graphs. Using tree formalisms for capturing linguistic aspects such as co-occurrence is not new: See, for example, the work by Joshi and Levy (1982) for the usage of trees to impose local constraints on sentences. Similarly, Carroll et al. (1999) investigate the practical implications of the extended domain of locality of tree-adjoining grammars.

Several formalisms have been put forth in the literature to describe graph-based semantic representations in general and AMR in particular. Most of these can be seen as variations of HRGs (see Habel and Kreowski 1987; Bauderon and Courcelle 1987; Drewes, Kreowski, and Habel 1997). It was established early that unrestricted HRGs can generate NP-complete graph languages (Aalbersberg, Rozenberg, and Ehrenfeucht 1986; Lange and Welzl 1987), so restrictions are needed to ensure efficient parsing. To this end, Lautemann (1990) proposes a CYK-like membership algorithm and proved that it runs in polynomial time provided that the language satisfies the following condition: For every graph G in the language, the number of connected components obtained by removing s nodes from G is in $O(logn)$⁠, where n is the number of nodes of G and the constant s depends on the grammar. Lautemann’s algorithm is refined by Chiang et al. (2013) to make it more suitable for natural language processing (NLP) tasks, but the algorithm is exponential in the node degree of the input graph.

In a parallel line of work, Quernheim and Knight (2012) propose automata on directed acyclic graphs (DAGs) for processing feature structures in machine translation. Chiang et al. (2018) invent an extended model of these DAG automata, focusing on semantic representations such as AMR. For this, the left- and right-hand sides in their DAG automata may take the form of restricted regular expressions. Blum and Drewes (2019) complement this work by studying language-theoretic properties of the DAG automata, establishing, among other things, that equivalence and emptiness are decidable in polynomial time.

Various types of graph algebras for AMR parsing are described in the work by Groschwitz et al. (see, e.g., Groschwitz, Koller, and Teichmann 2015; Groschwitz et al.2017,2018; Lindemann, Groschwitz, and Koller 2019,2020). A central objective is to find linguistically motivated restrictions that can efficiently be trained from data. An algorithm based on such an algebra for translating strings into semantic graphs is presented by Groschwitz et al. (2018): operations of arity zero denote graph fragments, and operations of arity two denote binary combinations of graph fragments into larger graphs. The trees over the operations of this algebra mirror the compositional structure of semantic graphs. The approach differs from ours in that their graph operations are entirely deterministic, and that neither context nodes nor cloning are used. Moreover, as is common in computational linguistics, evaluation is primarily empirical.

Through another set of syntactic restrictions on HRGs, Björklund et al. (2021) and Björklund, Drewes, and Ericson (2019) arrive at order-preserving DAG grammars (OPDGs)—with or without weights—which can be parsed in linear time. Intuitively, the restrictions ensure that each generated graph can be uniquely represented by a tree interpreted by a particular graph algebra. Despite their restrictions, OPDGs can describe central structural properties of AMR, but their limitation lies in the modeling of reentrancies. Of the previously discussed types of reentrancies, type (1) can to a large extent be modeled using OPDGs. Modeling type (2) cannot be done (except in very limited cases) since it requires attaching edges to the non-local context in a stochastic way, which cannot be achieved using hyperedge replacement alone.

The CHRGs by Drewes, Hoffmann, and Minas (2012) extend the ordinary HRGs with so-called contextual rules, which allow for isolated nodes in their left-hand sides. Contextual rules can reference previously generated nodes that are not attached to the replaced nonterminal hyperedge and add structure to them. Even though this formalism is strictly more powerful than HRG, it inherits several of the nice properties of HRG. In particular, there are useful normal forms and the membership problem is in NP (Drewes and Hoffmann 2015) for certain subclasses. However, as indicated above, the conditions defining these subclasses are semantic ones and thus difficult to handle. Here, we set out to use the idea of context nodes, enriched by a benign form of cloning, in a different way to develop a type of graph grammar that is sufficiently descriptive to model structural and non-structural phenomena in semantic graphs such as AMR, while allowing for easily verifiable syntactic conditions that result in polynomial time membership tests.

A very preliminary version of this work was published as Björklund, Drewes, and Jonsson (2021), the main result being a parsing algorithm that runs in time O(n^{2τ +1}) where τ is the maximal type of any extension operation in the grammar (see Sections 2 and 3 for definitions). The graph extension grammars in that version restrict the matching of context nodes to nodes in the argument graph solely via node labels (that is, their node labels have to be identical). The use of mso formulas for that purpose is more general, simplifies the formalism, and allows us to take advantage of Courcelle’s theorem in the main proof of the article while preserving the upper bound on the running time of O(n^{2τ +1}). Furthermore, it enables us to extend polynomial parsing to so-called local graph extension grammars. Their extension operations use a logical vocabulary enriched by so-called local node predicates, thus relaxing the assumption of edge agnosticism.

The remainder of this article is structured as follows. In the next section, we gather the basic definitions regarding graphs and logic on graphs. In Section 3 we introduce graph extension grammars and discuss an example. Section 4 shows that graph extension grammars can generate NP-complete graph languages. Readers who are less interested in NP-completeness results may safely skip that section, or consider it as another illustration of the concept of graph extension grammars. The major technical section is Section 5, in which we present the parsing algorithm and show that it can be implemented to run in polynomial time for edge-agnostic graph extension grammars. Subsequently, in Section 6, we show how the edge agnosticism requirement can be relaxed without sacrificing polynomial parsing, by turning to local graph extension grammars. Finally, Section 7 concludes.

We sometimes use boldface letters x to denote (finite) indexed sequences, whose individual elements are then denoted as x_i, that is, x = x₁⋯x_k where k = |x|. Alternatively, we may sometimes denote x_i by x(i).

A ranked alphabet is a pair A = (Σ, rk) such that Σ is a finite set of symbols and rk: Σ →ℕ is a function that assigns to every f ∈ Σ a rank. We usually keep rk implicit, thus notationally identifying A with Σ, and write f^(k) to indicate that rk(f) = k.

The set T_Σ of all well-formed trees over a ranked alphabet Σ is defined inductively: It is the smallest set of expressions such that, for every f^(k) ∈ Σ and all trees t₁,…, t_k ∈T_Σ, we have f[t₁,…, t_k] ∈T_Σ. In particular f[] for k = 0, which we henceforth abbreviate by f, is in T_Σ.

Let Σ be a ranked alphabet. A Σ-algebra is a pair $A=(A,(fA)f∈Σ)$ where $A$ is a set called the domain of $A$⁠, and $fA$ is a function $fA:Ak→A$ for every f^(k) ∈ Σ. Given a tree t ∈T_Σ, the result of evaluating t with respect to $A$ is denoted by $valA(t)$⁠: for t = f[t₁,…, t_k] we let $valA(t)=fA(valA(t1),…,valA(tk))$⁠.

To generate trees over the operations of an algebra, we use regular tree grammars.

While we are going to work with algebras over graph domains, let us illustrate the general idea by considering an algebra over the rational numbers ℚ. In this setting, the operations could be the standard arithmetic ones, such as +,−,/,×, all binary, together with constant-valued operations in ℚ, all of arity zero. It is hopefully easy to see how the trees $+[×[2,12],2]$ and /[10,−[10,4]] evaluate to 3 and $53$⁠, as they are mere syntactic variants of the common arithmetic expressions $(2×12)+2$ and 10/(10 −4), respectively.

We now define the type of graphs considered in this article, and the operations used to construct them. In short, we work with node- and edge-labeled directed graphs, each equipped with a sequence of so-called ports. From a graph operation point of view, the sequence of ports is the “interface” of the graph; its nodes are the only ones that can individually be accessed. The number of ports determines the type of the graph.

In the following, if the components of a graph G are not explicitly named, they will be denoted by V_G, E_G, lab_G, and port_G, respectively.

The restriction of a graph G to V ⊆ V_G and E ⊆ E_G is defined if [port_G] ⊆ V and $E⊆V×L-×V$⁠, and is in this case given by (V, E, lab|_V, port_G).

A morphism from a graph G = (V, E, lab, port) to a graph G′ = (V′, E′, lab′, port′) is a structure and label preserving function μ: V → V′. More precisely, we require that lab′(μ(v)) = lab(v) for all v ∈ V, (μ(u), z, μ(v)) ∈ E′ for all (u, z, v) ∈ E, and μ(port) is a prefix of port′ (that is, every port of G is mapped to the respective port of G′, but G′ may contain additional ports). The fact that μ is such a morphism is also denoted by writing μ: G → G′. G is included in G′, denoted by G ⊆ G′, if the identity on V is a morphism from G to G′.

A morphing of a graph G = (V, E, lab, port) into a graph G′ = (V′, E′, lab′, port′) is a surjective morphism μ: G → G′ which is also surjective on edges and ports, that is, E′ = {(μ(u), z, μ(v))∣(u, z, v) ∈ E} and port′ = μ(port). Given such a morphing, we denote G′ by μ(G), and call it a morph of G. A morphing is an isomorphism if it is bijective; if an isomorphism between G and G′ exists, then these graphs are isomorphic.

As described in Courcelle and Engelfriet (2012), graphs are examples of (finite) relational structures. Such a structure consists of a finite set of objects (in the case of graphs these are the nodes of the graph⁴) and a finite set of relations on these objects. Selecting the set of relations to be considered and their arities determines which type of structures we talk about. To be able to view (our type of) graphs as relational structures we need unary relations lab_a for every node label $a∈L̇$⁠, so that lab_a(v) is true if the node v carries the label a. We also need unary relations port_i for all port numbers i to express that a given node is the i-th port. Finally, we need binary relations edg_a for all $z∈L-$ in order to express that there is an edge labeled z between two nodes, that is, edg_z(u, v) is true if there is an edge labeled z from u to v.

The formal definition thus reads as follows:

We use predicate logic to express properties of (nodes in) graphs. While, in principle, any logic may be used, we focus on counting monadic second-order (cmso) logic. Thus, formulas can make use of individual and set variables, denoted by (possibly indexed) lowercase letters x, y,… and uppercase letters X, Y, …. In the following, we let $V0$ and $V1$ be disjoint countably infinite sets of individual and set variables, respectively. The set CMSO of all cmso formulas expressing graph properties is inductively defined to be the smallest set of formal expressions satisfying the following conditions:

• The formulas true and false are in CMSO.

• For all $x,y∈V0$⁠, $a∈L̇$⁠, $z∈L-$⁠, and i ∈ℕ, the formulas x = y, lab_a(x), edg_z(x, y), and port_i(x) belong to CMSO.

• For all $x∈V0$ and $X∈V1$⁠, the formula x ∈ X is in CMSO.

• For all $X∈V1$ and all r, s ∈ℕ with r < s, the formula card_{r, s}(X) is in CMSO.

• For all $ξ∈V0∪V1$⁠, Q ∈{∀,∃}, and formulas φ, φ′ ∈CMSO, the formulas (Q ξ.φ), (φ ∧ φ′), and (¬φ) belong to CMSO.

As usual, we can omit parentheses when writing down formulas if there is no danger of confusion.

A cmso formula φ may be denoted by φ(X, x), where $X∈V1⊛$ and $x∈V0⊛$⁠, to express the fact that the free variables occurring in φ are in [X] ∪ [x].⁶ Given a graph G, an assignment appropriate for a formula φ(X, x) is a mapping asg that assigns a subset of V_G to every X ∈ [X] and an element of V_G to every x ∈ [x]. Given such an assignment, φ can be evaluated in G in the usual way, where card_{r, s}(X) (with X ∈X) is satisfied if and only if |asg(X)| = r (mod s). If asg(X) = V and asg(x) = v, we let $G⊨φ(V,v)$ denote the statement that φ is satisfied (i.e., evaluates to true) in G under asg. As usual, we can make use of other Boolean connectives such as ∨ and → in formulas since they can be expressed in terms of ∧ and ¬. For example, for cmso formulas φ and φ′, the formula $φ→φ′$ is equivalent to ¬(φ ∧¬φ′), in the sense that the two formulas are satisfied by the same set of assignments, and φ ∨ φ′ is equivalent to ¬(¬φ ∧¬φ′).

In Section 5, we will make use of the so-called Backwards Translation theorem for quantifier-free operations. These quantifier-free operations map relational structures to other relational structures, in our case graphs to graphs. The formal definition of these operations takes some getting used to (as so much in the area of formal logic). In the next paragraphs, we thus try to convey the intuition first. However, we would also like to point out that quantifier-free operations and the Backwards Translation theorem are “merely” technical tools we use to formulate the proof of our main result. They are not used in the graph extension grammars themselves. Hence, readers who are just interested in the formalism and the overall parsing strategy may safely skip the remainder of this section.

The idea behind quantifier-free operations, which is a special case of the more general cmso operations, is to use a collection of logical formulas to describe a mapping from one type of relational structure to another. Hence, the input is a relational structure consisting of a set of objects (like the nodes of a graph) and a number of relations on these objects. The output is supposed to be a similar relational structure, though in general it can be a structure involving other relations. Now, we can use logical formulas to define both the domain of the resulting structure and each of its relations in terms of the input structure. For this, we need two things:

1. a domain formula δ with one free individual variable (the “argument” of the formula) which, when applied to an object in the input structure, determines whether this object is to be an object in the output structure (value true) or not (value false);⁷

2. for every relation R_i of the output structure, a formula $θRi$ with β_i free variables, where β_i is the arity of R_i. If this formula, applied to objects $v1,…,vβi$ of the input structure, yields true, then $(v1,…,vβi)$ is a tuple in the relation R_i of the output structure (provided that all of $v1,…,vβi$ are in its domain, as dictated by the domain formula).

Naturally, both the domain formula and the formulas determining the output relations can make use of the relations of the input structure. The mappings definable in this way are called quantifier-free operations because we shall forbid the formulas to make use of quantifiers.

We are actually only interested in the case where both input and output structures are graphs. Hence, the purpose of δ is to pick the nodes to be included in the output graph, while the formulas $θRi$ define its node labels, edges, and ports.

The following formal definition provides one more element, which for simplicity was left out in the explanation above: A quantifier-free operation can have additional parameters. These parameters are represented by free set variables X₁,…, X_ℓ in the formulas and are thus to be instantiated by sets of nodes of the input graph when the operation is “called”. Hence, the operation can yield different output graphs for one and the same input graph depending on those parameters. In later parts of the article, these parameters will be used to be able to select certain nodes that are meant to play a distinguished role in the construction formalized by the operation.

We note here that the quantifier-free operations defined in Courcelle and Engelfriet (2012) satisfy ℓ = 0, that is, they do not depend on arguments U₁,…,U_ℓ. However, the extension to ℓ ≥ 0 will turn out to be technically convenient and is mathematically insignificant because one can alternatively consider relational structures with additional unary predicates U₁,…,U_ℓ to achieve the same effect in the setting of Courcelle and Engelfriet (2012). A similar remark applies to Theorem 1 below.

Now we can state the Backwards Translation theorem (which is a weak version of a similar theorem for the much more general CMSO-transductions [Courcelle and Engelfriet 2012, Theorem 7.10]). This theorem states that, if we have a quantifier-free operation ξ, any property of ξ(G) that can be expressed by some cmso formula φ can also be expressed as a property of the original graph G by means of a cmso formula φ′ (obtained by, intuitively, “backwards translating” φ along ξ).

Graph extension grammars generate graphs by repeated application of two types of graph operations. One type of operation takes the disjoint union of a pair of smaller graphs, in doing so concatenating their port sequences. The other type extends an existing graph with additional structure placed “on top” of that graph. The extension operation uses a template graph with designated nodes, so-called docks. The docks are to be attached to the ports of the argument graph, and the ports of the template become the ports of the combined graph. The template also contains a number of context nodes that can be duplicated (or cloned) and identified with arbitrarily chosen nodes in the argument graph. This is provided that the choice satisfies a given formula whose free variables are the targets of the cloned context nodes.

To formally define the simpler one of these graph operations, disjoint union, let k, k′ ∈ℕ. Then $⊎kk′:Gk×Gk′→Gk+k′$ is defined as follows: for $G∈Gk$ and $G′∈Gk′$⁠, ⊎_kk′(G, G′) yields the graph in $Gk+k′$ obtained by making the two graphs disjoint by a suitable renaming of nodes and taking their union. This is defined in the obvious way for the first three components of the argument graphs and concatenates the port sequences of both graphs. Thus, ⊎_kk′ is not commutative and only defined up to isomorphism. We usually write G ⊎_kk′G′ instead of ⊎_kk′(G, G′). To avoid unnecessary technicalities, we shall generally assume that G and G′ are disjoint from the start, and that no renaming of nodes takes place. We extend ⊎_kk′ to an operation $⊎kk′:℘(Gk)×℘(Gk′)→℘(Gk+k′)$ in the usual way: for $G⊆Gk$ and $G′∈Gk′$⁠, $G⊎kk′G′={G⊎kk′G′∣G∈G,G′∈G′}$⁠.

To introduce the second type of graph operation, we first define cloning. The purpose of cloning is to make the expansion operations (to be defined afterwards) more powerful by allowing them to attach edges to an arbitrary number of nodes in the argument graph. Cloning of nodes was originally introduced to formalize the structure of object-oriented programs (Drewes et al. 2010), and later adopted in computational linguistics (Björklund, Drewes, and Ericson 2019).

To define cloning, consider a graph G = (V, E, lab, port) and let C ⊆ V ∖ [port]. Then clone_C(G) is the set of all graphs obtained from G by replacing each of the nodes in C and their incident edges by an arbitrary number of copies. Figure 4 illustrates this construction. Formally, G′ = (V′, E′, lab′, port′) ∈clone_C(G) if there is a family (CL_v)_v∈V of pairwise disjoint sets CL_v of nodes, such that the following hold:

• CL_v = {v} for all v ∈ V ∖ C,

• $V′=⋃v∈VCLv$⁠,

• $E′=⋃(u,z,v)∈ECLu×{z}×CLv$⁠, and

• for all v ∈ V and v′ ∈CL_v, lab′(v′) = lab(v).

Note that cloning does not rename nodes in V ∖ C. In the following, we shall continue to denote by CL_v (v ∈ V) the set of clones of v in a graph belonging to clone_C(G).

For notational convenience, we define two abbreviations:

• C_Φ = V_Φ ∖ ([port_Φ] ∪ [dock_Φ]) is the set of context nodes and

• NEW_Φ = [port_Φ] ∖ [dock_Φ] is the set of new nodes.

We assume in the following that the set C_Φ is implicitly ordered, so that we can view it as a sequence whenever convenient. Thus, if C_Φ = {v₁,…, v_k}, the last component of Φ has the form $φΦ(Xv1⋯Xvk)$ with one set variable $Xvi$ for every context node v_i.

Throughout the rest of this article, we shall continue to denote the components of an expansion operation Φ by V_Φ, E_Φ, lab_Φ, port_Φ, dock_Φ, C_Φ, and φ_Φ.

When applied to a graph, Φ adds (copies of the) nodes in NEW_Φ to the graph while those in [dock_Φ] and C_Φ are references to ports and nondeterministically chosen nodes in the input graph, respectively.

Formally, the application of Φ to an argument graph $G=(V,E,lab,port)∈Gℓ$ is possible if |dock_Φ| = ℓ. It yields a graph of type |port_Φ| by fusing the nodes in dock_Φ with those in port. Moreover, clones of the context nodes are fused with arbitrary nodes in V, inheriting the labels from G. Thus, the application of the operation to G clones the nodes in C_Φ, fuses those in dock_Φ with those in port, and fuses all nodes in CL_v, for each v ∈ C_Φ, injectively with nodes in V, provided that φ_Φ is satisfied under the assignment given by the mapping of cloned context nodes to nodes in V. The port sequence of the resulting graph is port_Φ.

Formally, let |port_Φ| = k and |dock_Φ| = ℓ. Then Φ is interpreted as the nondeterministic operation $Φ:Gℓ→℘(Gk)$ defined as follows. For a graph $G=(V,E,lab,port)∈Gℓ$⁠, a graph $H∈Gk$ is in Φ(G) if it can be obtained by the following steps:

1. Choose a graph $G′∈cloneCΦ(Φ̲)$ and a morphing μ of G′ to a graph (V′, E′, lab′, port′) such that the following hold:

   • (a)

     μ(NEW_Φ) ∩ V = ∅,

   • (b)

     μ(dock_Φ) = port,

   • (c)

     for all nodes v ∈ C_Φ, it holds that μ(CL_v) ⊆ V, and

   • (d)

     $G⊨φΦ(μ(CΦ))$ (where we view C_Φ as a sequence).

2. Define H = (V ∪ V′, E ∪ E′, lab ⊔lab′, port′).

We observe that by the definition of the priority union ⊔, the labels of nodes not belonging to NEW_Φ are disregarded. Hence, the labels of nodes that are fused with context nodes or are ports in G are determined by lab.⁸ This means that the labels of nodes not in NEW_Φ can be dropped when specifying Φ, essentially regarding these nodes as unlabeled ones.

We now specialize expansion operations to extension operations by placing conditions on their structure. The intuition is to make sure that graphs are built bottom–up, that is, that Φ always extends the input graph by placing nodes and edges “on top”, with edges being directed downwards, and in such a way that all nodes of the argument graph are reachable from the ports. For this purpose, edges must point from new to “old” nodes, and all nodes in [dock_Φ] which are not in [port_Φ] (i.e., intuitively, ports in the argument graph that are “forgotten”) must have an incoming edge. Formally,

• (R1)

  $EΦ⊆NEWΦ×L-×(VΦ∖NEWΦ)$ and

• (R2)

  [dock_Φ] ∖ [port_Φ] ⊆ tar(E_Φ).

Since edges introduced by an extension operation, owing to (R1), can only be directed from new nodes (which by definition of NEW_Φ must be ports) to nodes in the argument graph, it follows in particular that all graphs constructed from the empty graph with the help of union and extension operations are directed acyclic graphs (DAGs). By a straightforward induction, (R2) ensures that every node in a graph constructed in this way is reachable from a port.

A graph extension algebra is a Σ-algebra $A=(℘(G),(fA)f∈Σ)$ where every symbol in Σ is interpreted as an extension operation, a union operation, or the set {ϕ}, where ϕ is the empty graph (∅, ∅, ∅, ε). Note that the operations of the algebra act on sets of graphs rather than on single graphs. This is necessary because of the nondeterministic nature of extension operations. It also takes care of the fact that operations are only defined on graphs of the right type: By convention, the application of an operation to a graph of an inappropriate type yields the empty set of results. This relieves us from having to deal with typed algebras.

For notational simplicity, we shall assume that, in a graph extension grammar as above, $f=fA$ for all f ∈ Σ, that is, we use the operations themselves as symbols in Σ.

Before entering on the topic of parsing, let us pause to consider a concrete example in the setting of natural language processing.

Readers familiar with HRGs or Courcelle’s hyperedge replacement algebras (Courcelle 1991) may have noticed that productions using union and extension operations (disregarding context nodes and the effect of the component φ_Φ) correspond to hyperedge replacement productions of two types:

• (a) 

  A → B ⊎_kℓC corresponds to a production with two hyperedges in the right-hand side, labeled B and C, where the first one is attached to k of the nodes to which the nonterminal in the left-hand side (which is labeled A) is attached, and the second is attached to the remaining ℓ nodes of the left-hand side. In particular, there are no further nodes in the right-hand side.

• (b) 

  A → Φ[B] corresponds to a hyperedge replacement production with a single nonterminal hyperedge labeled B in its right-hand side. Such productions are the ones responsible for actually generating new terminal items (nodes and edges).

Generalized extension operations of arity greater than one can be constructed by defining so-called derived operations through composition of suitable extension and union operations. Given a set of such derived operations, the tree-to-tree mapping that replaces each occurrence of a derived operation by its definition is a tree homomorphism. As regular tree languages are closed under tree homomorphisms, this shows that the restriction to binary unions and unary extensions is no limitation (in contrast to requirements (R1) and (R2), which help reduce the complexity of parsing).

We also remark here that it is not a restriction that all new nodes introduced in an extension operation are ports. This is because we can add a non-port to a graph G by evaluating Φ(Φ′(G)) where Φ′ introduces the desired node as a port, say port i, and Φ “forgets” port i, that is, dock_Φ(i)∉[port_Φ]. (Note, however, that (R2) then requires dock_Φ(i) to have an incoming edge from one of the ports of Φ, making sure that the node introduced in this way is reachable from a port in Φ(Φ′(G)).)

Before turning to graph extension grammars for which parsing can be implemented to run in polynomial time, we confirm in this section that restrictions are required to accomplish this (unless P = NP), as the problem is NP-complete in general. Readers who are not interested in the proof may either skip this section or read it for the sake of seeing another example of a graph extension grammar.

We note that the validity of the preceding proof does not depend on the use of isolated context nodes in Φ_sat: The proof remains valid if we add (equally labeled) edges from the port to each of these context nodes. Then every node corresponding to a subformula would receive exactly one incoming edge from the port, regardless of the truth assignment hidden in the choice of X_T and X_F, and adding those edges to the output graph G′ of the reduction would again result in a logspace reduction to L(Γ).

We now provide a blueprint of a parsing algorithm for graph extension grammars, which we afterwards instantiate to a polynomial time parsing algorithm for a special case of graph extension grammars, the so-called edge-agnostic ones. In the next section, we will discuss how this restriction can partially be lifted.

The goal is to decide the membership problem for L(Γ) and, in the positive case, produce a corresponding derivation tree t ∈ L(g) such that the given graph G is in $valA(t)$⁠. In fact, by the recursive structure of the proposed algorithm, it will be obvious how to obtain t. Hence, we focus on the membership problem, which is formally defined as follows:

• Input: 

  A graph G

• Question: 

  Does it hold that G ∈ L(Γ)?

By definition, extension operations keep the identities of nodes in the input graph unchanged, whereas new nodes added to the graph may be given arbitrary identities (as long as clashes with nodes in the input graph are avoided). For the union operation, it holds that renaming of nodes is necessary only if the node sets of the two argument graphs intersect. As a consequence, when evaluating a tree t, we can without loss of generality assume that operations never change node identities of argument graphs. In other words, if $G∈valA(t)$⁠, then for every α ∈ addr(t), there is a (concrete) graph $Gα∈valA(t/α)$ such that

• if t/α = Φ[t/α1], then G_α ∈ Φ(G_α1) and

• if t/α = t/α1 ⊎_kℓt/α2, we have G_α = (V₁ ∪ V₂, E₁ ∪ E₂, lab₁ ⊔lab₂, port₁, port₂) where G_αi = (V_i, E_i, lab_i, port_i) for i = 1,2,

and G_ε = G.

Thus, for every α ∈ addr(t), the graph G_α is a subgraph of G. More precisely, if G = (V, E, lab, port) and G_α = (V′, E′, lab′, port′) then V′ ⊆ V, E′ ⊆ E, and lab′ = lab|_V′. Note that, while the graphs G_α are usually not uniquely determined by G and t, the important fact is that they do exist if and only if $G∈valA(t)$⁠. We say in the following that the family (G_α)_α∈addr(t) is a concrete evaluation of t into G. Hence, the membership problem amounts to deciding, for the input graph G, whether there is a tree t ∈ L(g) that permits a concrete evaluation into G.

The following lemma, which forms the basis of our parsing algorithm, shows that G_α = (V′, E′, lab′, port′) is determined by port′ alone, as it is the subgraph of G induced by the nodes that are reachable from port′. More precisely, consider a sequence $p∈V⊛$ of nodes of G and let $p▿$ be the set of nodes reachable in G by directed paths from (any of the nodes in) p.⁹ Now, we define $G▿p=(p▿,E∣p▿×L-×p▿,lab∣p▿,p)$⁠.

We prove Claim 1 by induction on the length of α. (Thus, the induction proceeds top-down rather than bottom-up.) For α = ε, the statement holds trivially. Now, assume that it holds for some α ∈ addr(t). Since the empty graph ϕ has neither ports nor edges, two relevant cases remain.

Let {i, j} = [2]. We have to show that the statement holds for G_αi. Thus, assume that src(e) ∈ V_αi and $v∈portαi▿$⁠. Then src(e) ∈ V_α and thus, by the induction hypothesis, e ∈ E_α. By the definition of ⊎_kℓ this means that e ∈ E_αi. Furthermore, $v∈portαi▿$ implies $v∈portα▿$ and thus, again by the induction hypothesis, v ∈ V_α. Hence, it remains to argue that no node in G_αj can be reached from port_αi. This follows readily from the just established fact that there is no edge e′ ∈ V ∖ V_αi for which src(e′) ∈ E_αi (together with the fact that V_αi ∩ V_αj = ∅).

To show that the statement holds for G_α1, let G_α = (V_α1 ∪ V′, E_α1 ∪ E′, lab_α1 ⊔lab′, port′), where (V′, E′, lab′, port′) is obtained from $Φ̲$ as in the definition of Φ(G_α1). By the induction hypothesis, src(e) ∈ V_α implies e ∈ E_α. Thus, src(e) ∈ V_α1 implies e ∈ E_α1 unless e ∈ E′. However, by requirement (R1), all e ∈ E′ satisfy src(e) ∈ [port′] ∖ [port], which is equivalent to src(e)∉V_α1 because V_α ∖ V_α1 = [port′] ∖ [port]. From this it follows that e ∈ E_α1.

Now, let $v∈portα1▿$⁠. If v∉V_α1, consider the first edge e on a path from a node in [port_α1] to v such that tar(e)∉V_α1. Then src(e) ∈ V_α1 but e∉E_α1, contradicting the previously established fact that src(e) ∈ V_α1 implies e∉E_α1.

This finishes the proof of Claim 1. Next, we prove the converse inclusion of the second part of Claim 1:

This time, we proceed bottom–up, by induction on the size of t/α. The statement is trivially true for G_α = ϕ. Thus, as before, there are two cases to distinguish.

By the induction hypothesis, Claim 2 holds for G_α1 and G_α2. Consequently, $Vα=Vα1∪Vα2⊆portα1▿∪portα2▿=portα▿$⁠.

Again, let G_α = (V_α1 ∪ V′, E_α1 ∪ E′, lab_α1 ⊔lab′, port′), where (V′, E′, lab′, port′) is obtained from $Φ̲$ as in the definition of Φ(G_α1). (In particular, port′ = port_α.) By the induction hypothesis, $Vα1⊆portα1▿$⁠. Moreover, by requirement (R2), for every node v ∈ [port_α1] it either holds that v ∈ [port_α], or there are u ∈ [port_α] and e ∈ E′ with src(e) = u and tar(e) = v. Hence, $[portα1]⊆portα▿$ and thus $Vα1⊆portα1▿⊆portα▿$⁠. Since, furthermore, V′∖ V_α1 ⊆ [port_α], this shows that V_α ⊆ [port_α], and thus $Vα⊆portα▿$⁠.

Together, Claims 1 and 2 state that V_α contains exactly the nodes reachable from port_α (by Claim 2 and the second part of Claim 1), and also all edges originating at those nodes (by the first part of Claim 1). This finishes the proof of the lemma.

We note the following immediate consequence of Lemma 1:

In Lemma 1, we find the beginnings of a recursive parsing algorithm: In the following, consider an input graph G = (V, E, lab, port), a nonterminal A ∈ N, and a sequence $p∈V⊛$⁠. To decide whether $G▿p∈valA(LA(g))$ (and thus whether G ∈ L(Γ) if A = S and p = port_G), we need to consider three cases, the first two of which are straightforward.

Otherwise, we need to check each production with the left-hand side A according to Cases 2 and 3, as follows:

To define the notion of matchings, consider a graph extension operation Φ with |port_Φ| = k, as well as a directed acyclic graph H with type(H) = k (i.e., here H takes the rôle of $G▿p$ above). We need to determine all possible $p1∈VH⊛$ such that $H∈Φ(H▿p1)$⁠. To see how this can be done, let V_NEW = {port_H(i)∣i ∈ [k]and port_Φ(i)∉[dock_Φ]}. In other words, V_NEW is the set of nodes of H which are images of nodes in NEW_Φ. Recall that, by (R1), the nodes in NEW_Φ are the only nodes in Φ that may have edges to other nodes in Φ. Thus, the edge set E_NEW = {e ∈ E_H∣src(e) ∈ V_NEW} contains precisely the edges of H which are images of edges of Φ. Hence, we have to find a suitable mapping of the nodes in V_Φ to subsets of $V1=p1▿$⁠. We say that a function m: V_Φ → ℘(V₁) is a matching of Φ to H if the following conditions are satisfied:

• (M1) 

  The restriction of H to V₁ and E_NEW is a morph of a graph in $cloneCΦ(Φ̲)$ by some morphing μ which satisfies the conditions |μ(CL_u)| = 1 for all u ∈dock_Φ and μ(CL_v) = m(v) for all v ∈ V_Φ.

  (In particular, |m(v)| = 1 for all v ∈ [port_Φ] ∪ [dock_Φ]. Therefore, we shall in the following view the restriction of m to [port_Φ] ∪ [dock_Φ] as a function from nodes to nodes rather than to sets of nodes, see, for example, (M2) and the left-hand side of (M3) below.)

• (M2) 

  In H, every node in V_H ∖ [port_H] is reachable from (a node in) m(dock_Φ).

• (M3) 

  $H▿m(dockΦ)⊨φΦ(m(u1),…,m(un))$⁠, where {u₁,…, u_n} = C_Φ.

The pseudocode of the algorithm is shown in Algorithm 1. In the code, we use the statement “returnresult[A, p]← true” to denote memoisation: the variable result[A, p] gets the Boolean value true assigned to it and then that same value is returned by the procedure. Obviously, the condition in line 21 of the algorithm needs to be made more concrete, that is, we have to find (efficient) ways to check whether m exists. However, let us first postpone this question and show that the algorithm is correct.

The remainder of the article will be devoted to the question of how line 21 can be concertized. In this section, this will first result in a polynomial-time algorithm for the special case of edge-agnostic graph extension grammars (to be defined formally in Definition 7). With this as a basis, the next section will generalize the result to local graph extension grammars.

For a fixed grammar, thanks to memoisation Parse_rec will be called at most O(n^wd(Γ)) times, where n is the number of nodes of the input graph. This is because there are only a constant number of possible choices for the first parameter and n^wd(Γ) for the second. Hence, the total running time is O(n^wd(Γ)) times the maximal number of computation steps it takes to execute the body of the procedure (not counting recursive calls). This, in turn, is dominated by the time it takes to enumerate the matchings m of Φ to $G▿p$ (line 21). For this, note that there is no need for line 21 to explicitly enumerate all matchings m of Φ to $G▿p$ because the loop body only depends on (the nonterminal B and) m(dock_Φ). In other words, the loop can be replaced with

Hence, the question that remains is how to implement line 22’, that is, to decide for given $p,d∈V⊛$ whether there exists a matching m of Φ to $G▿p$ with m(dock_Φ) = d. For this, we will now show that one can construct a cmso formula that checks whether the mapping of dock_Φ to d can be extended to a matching of Φ to $G▿p$⁠. (This makes it possible to use Courcelle’s theorem to come up with an efficient algorithm for the edge-agnostic case of graph extension grammars later on.)