{'fraction_non_alphanumeric': 0.040939193257074055, 'fraction_numerical': 0.010730601692814392, 'mean_word_length': 4.403367776502105, 'pattern_counts': {'":': 1, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Semantic construction with graph grammars

We introduce s-graph grammars, a new grammar formalism for computing graph-based semantic representations. Semantically annotated corpora which use graphs as semantic representations have recently become available, and there have been a number of data-driven systems for semantic parsing that can be trained on these corpora. However, it is hard to map the linguistic assumptions of these systems onto more classical insights on semantic construction. S-graph grammars use graphs as semantic representations, in a way that is consistent with more classical views on semantic construction. We illustrate this with a number of hand-written toy grammars, sketch the use of s-graph grammars for data-driven semantic parsing, and discuss formal aspects.


Introduction
Semantic construction is the problem of deriving a formal semantic representation from a natural-language expression. The classical approach, starting with Montague (1974), is to derive semantic representations from syntactic analyses using hand-written rules. More recently, semantic construction has enjoyed renewed attention in mainstream computational linguistics in the form of semantic parsing (see e.g. Wong and Mooney, 2007;Zettlemoyer and Collins, 2005;Chiang et al., 2013). The idea in semantic parsing is to make a system learn the mapping of the string into the semantic representation automatically, with or without the use of an explicit syntactic representation as an intermediate step. The focus is thus on automatically induced grammars, if the grammar is not left implicit altogether.
Training such data-driven models requires semantically annotated corpora. One recent development is the release of several corpora in which English sentences were annotated with graphs that represent the meanings of the sentences (Banarescu et al., 2013;Oepen et al., 2014). There has already been a body of research on semantic parsing for graphs based on these corpora, but so far, the ideas underlying these semantic parsers have not been connected to classical approaches to semantic construction. Flanigan et al. (2014) and Martins and Almeida (2014) show how to adapt data-driven dependency parsers from trees to graphs. These approaches do not use explicit grammars, in contrast to all work in the classical tradition. Chiang et al. (2013) do use explicit Hyperedge Replacement Grammars (HRGs, Drewes et al., 1997) for semantic parsing. However, HRGs capture semantic dependencies in a way that is not easily mapped to conventional intuitions about semantic construction, and indeed their use in linguistically motivated models of the syntax-semantics interface has not yet been demonstrated.
But just because we use graphs as semantic representations and learn grammars from graph-banks does not mean we need to give up linguistic insights from several decades of research in computational semantics. In this paper, we address this challenge by presenting s-graph grammars. S-graph grammars are a new synchronous grammar formalism that relates strings and graphs. At the center of a grammatical structure of an s-graph grammar sits a derivation tree, which is simultaneously interpreted into a string (in a way that is equivalent to context-free grammar) and into a graph (in a way that is equivalent to HRGs). Because of these equivalences, methods for statistical parsing and grammar induction transfer from these formalisms to s-graph grammars. At the same time, s-graph grammars make use of an explicit inventory of semantic argument positions. Thus they also lend themselves to writing linguistically interpretable grammars by hand.
The paper is structured as follows. In Section 2, we will briefly review the state of the art in semantic parsing, especially for graph-based semantic representations. We will also introduce Interpreted Regular Tree Grammars (IRTGs) (Koller and Kuhlmann, 2011), which will serve as the formal foundation of sgraph grammars. In Section 3, we will then define s-graph grammars as IRTGs with an interpretation into the algebra of s-graphs (Courcelle and Engelfriet, 2012). In Section 4, we will illustrate the linguistic use of s-graph grammars by giving toy grammars for a number of semantic phenomena. We conclude by discussing a number of formal aspects, such as parsing complexity, training, and the equivalence to HRG in Section 5.

Previous Work
We start by reviewing some related work.

Semantic construction and semantic parsing
In this paper, we take "semantic construction" to mean the process of deriving a semantic representation from a natural-language string. Semantic construction has a long tradition in computational semantics, starting with Montague (1974), who used higher-order logic as a semantic representation formalism.
Under the traditional view, the input representation of the semantic construction process is a syntactic parse tree; see e.g. Blackburn and Bos (2005) for a detailed presentation. One key challenge is to make sure that a semantic predicate combines with its semantic arguments correctly. In Montague Grammar, this is achieved by constructing through functional application of a suitably constructed lambda-term for the functor. Many unification-based approaches to semantic construction, e.g. in the context of HPSG (Copestake et al., 2001), TAG (Gardent and Kallmeyer, 2003), and CCG (Baldridge and Kruijff, 2002) use explicit argument slots that are identified either by a globally valid name (such as "subject") or by a syntactic argument position. Copestake et al. (2001), in particular, conclude from their experiences from designing large-scale HPSG grammars that explicitly named arguments simplify the specification of the syntax-semantics interface and allow rules that generalize better over different syntactic structures. Their semantic algebra assigns to each syntactic constituent a semantic representation consisting of an MRS, together with hooks that make specific variable names of the MRS available under globally available names such as "subject", "object", and so on. The algebra then provides operations for combining such representations; for instance, the "combine with subject" operation will unify the root variable of the subject MRS with the variable with the name "subject" of the verb MRS. Like this standard approach, and unlike the HRG approach described below, this paper identifies semantic argument positions by name as well, and extends this idea to graph-based semantic representations.
Recently, semantic construction has resurfaced in mainstream computational linguistics as "semantic parsing". Here the focus is on directly learning the mapping from strings to semantic representations from corpora, with or without the use of an explicit syntactic grammar. The mapping can be represented in terms of synchronous grammars (e.g. Wong and Mooney, 2007) or CCG (e.g. Zettlemoyer and Collins, 2005). Both of these lines of research have so far focused on deriving lambda terms, and are not obviously applicable to deriving graphs.

Graphs as semantic representations
The recent data-driven turn of semantic parsing motivates the development of a number of semantically annotated corpora ("sembanks"). Traditional semantic representations, such as higher-order logic, have shown to be challenging to annotate. Even the Groningen Meaning Bank (Bos et al., 2014), the bestknown attempt at annotating a corpus with traditional semantic representations (DRT), uses a semiautomatic approach to semantic annotation, in which outputs of the Boxer system (Curran et al., 2007) are hand-corrected. A larger portion of recent sembanks use graphs as semantic representations. This strikes a middle ground, which is mostly restricted to predicate-argument structure, but can cover phenomena such as control, coordination, and coreference. In this paper, we will take the hand-annotated graphs of the AMR-Bank (Banarescu et al., 2013) as our starting point. These abstract meaning representations (AMRs; see the example in Fig. 1) use edge labels to indicate semantic roles, including ones for semantic arguments (such as "ARG0", "ARG1", etc.) and ones for modification (such as "time", "manner", etc.). Graphs are also used as semantic representations in the semantic dependency graphs from the SemEval-2014 Shared Task (Oepen et al., 2014). These are either manually constructed or converted from deep semantic analyses using large-scale HPSG grammars. The recent availability of graph-based sembanks has triggered some research on semantic parsing into graphs. Flanigan et al. (2014) and Martins and Almeida (2014) do this by adapting dependency parsers to compute dependency graphs rather than dependency trees. They predict graph edges from corpus statistics, and do not use an explicit grammar; they are thus very different from traditional approaches to semantic construction. Chiang et al. (2013) present a statistical parser for synchronous string/graph grammars based on hyperedge replacement grammars (HRGs, Drewes et al., 1997). HRGs manipulate hypergraphs, which may contain hyperedges with an arbitrary number k of endpoints, labeled with nonterminal symbols. Each rule application replaces one such hyperedge with the graph on the right-hand side, identifying the endpoints of the nonterminal hyperedge with the "external nodes" of the graph. Jones et al. (2012) and Jones et al. (2013) describe a number of ways to infer HRGs from corpora. However, previous work has not demonstrated the suitability of HRG for linguistically motivated semantic construction. Typical published examples, such as the HRG rules from Chiang et al. (2013) shown in Fig. 1 on the right, are designed for succinctness of explanation, not for linguistic adequacy (in the figure, the external nodes are drawn shaded). Part of the problem is that HRG rules take a primarily top-down perspective on graph construction (in contrast to most work on compositional semantic construction) and combine arbitrarily complex substructures in single steps: the Y hyperedge in the first example rule is like a higher-order lambda variable that will be applied to three nodes introduced in that rule. The grammar formalism we introduce here builds graphs bottom-up, using a small inventory of simple graph-combining operations, and uses names for semantic argument positions that are much longer-lived than the "external nodes" of HRG.

Interpreted regular tree grammars
This paper introduces synchronous string/graph grammars based on interpreted regular tree grammars (IRTGs; Koller and Kuhlmann, 2011). We give an informal review of IRTGs here. For a more precise definition, see Koller and Kuhlmann (2011).
Informally speaking, an IRTG G = (G, (h 1 , A 1 ), . . . , (h k , A k )) derives a language k-tuples of objects, such as strings, trees, or graphs (see the example in Fig. 2). It does this in two conceptual steps. First, we build a derivation tree using a regular tree grammar G. Regular tree grammars (RTGs; see RTG rule homomorphisms S → r 1 (NP, VP) 1:  e.g. Comon et al., 2008, for an introduction) are devices for generating trees by successively replacing nonterminals using production rules. For instance, the RTG in the left column of Fig. 2 can derive the derivation tree t shown at the top right from the start symbol S.
In a second step, we can then interpret t into a tuple (a 1 , . . . , a k ) ∈ A 1 × . . . × A k of elements from the algebras A 1 , . . . , A k . An algebra A i is defined over some set A i , and can evaluate terms built from some signature ∆ i into elements of A i . For instance, the string algebra T * contains all strings over some finite alphabet T . Its signature contains two types of operations. Each element a of T is a zero-place operation, which evaluates to itself, i.e. John = John. Furthermore, there is one binary operation •, which evaluates to the binary concatenation function •(t 1 , t 2 ) = w 1 w 2 where w i = t i . Each term built from these operation symbols evaluates to a string in T * ; for instance, at the lower right of Fig. 2, the term (John•(opens•the box)) evaluates to the string John•(opens•the box) = "John opens the box".
An IRTG derives elements of the algebras by mapping, for each interpretation 1 ≤ i ≤ k, the derivation tree t to a term h i (t) over the algebra using a tree homomorphism h i . The tree homomorphisms are defined in the right-hand column of the table in Fig. 2; for instance, we have h 1 (r 2 ) = x 1 • x 2 (which concatenates the V-string with the NP-string, in this order) and h 2 (r 2 ) = x 2 • x 1 (which puts the NPstring before the V-string). It then evaluates h i (t) over the algebra A i , obtaining an element of A i . Altogether, the language of an IRTG is defined as In the example, the pair John opens the box, Hansöffnet die Kiste is one element of L(G). Generally, IRTGs with two string-algebra interpretations are strongly equivalent to synchronous context-free grammars, just as IRTGs with a single string-algebra interpretation represent context-free grammars. By choosing different algebras, IRTGs can also represent (synchronous) tree-adjoining grammars (Koller and Kuhlmann, 2012), tree-to-string transducers (Büchse et al., 2013), etc.

An algebra of s-graphs
We can use IRTGs to describe mappings between strings and graph-based semantic representations. Let an s-graph grammar be an IRTG with two interpretations: one interpretation (h s , T * ) into a string algebra T * as described above, and one interpretation (h g , A g ) into an algebra A g of graphs. In this section, we define a graph algebra for this purpose.
The graph algebra we use here is the HR algebra of Courcelle (1993), see also Courcelle and Engelfriet (2012). The values of the HR algebra are s-graphs. An s-graph G is a directed graph with node Figure 3: Example s-graphs.
labels and edge labels in which each node may be marked with a set of source names s ∈ S from some fixed finite set S. 1 At most one node in an s-graph may be labeled with each source name s; we call it the s-source of G. We call those nodes of G that carry at least one source name the sources of G.
When we use s-graphs as semantic representations, the source names represent the different possible semantic argument positions of our grammar. Consider, for example, the s-graphs shown in Fig. 3. G 3 comes from the lexicon entry of the verb "sleep": It has a node with label "sleep", with an ARG0-edge into an unlabeled node. The "sleep"-node carries the source name root, indicating that this node is the "root", or starting point, of this semantic representation. (We draw source nodes shaded and annotate them with their source names in angle brackets.) We will ensure that every s-graph we use has a rootsource; note that this node may still have incoming edges. The other node is the subj-source of the s-graph; this is where we will later insert the root-source of the grammatical subject. Similarly, G 1 has three sources: next to the labeled root, it has has two further unlabeled sources for the subj and vcomp argument, respectively.
The HR algebra defines a number of operations for combining s-graphs which are useful in semantic construction.
• The rename operation, G[a 1 → b 1 , . . . , a n → b n ], evaluates to a graph G that is like G -except that for all i, the a i -source of G is now no longer an a i -source, but a b i -source. All the n renames are performed in parallel. The operation is only defined if for all i, G has a a i -source, and either there is no b i -source or b i is renamed away (i.e., b i = a k for some k). Because we use the source name root so frequently, we write G[b] as shorthand for G[root → b].
• The forget operation, f a 1 ,...,an (G), evaluates to a graph G that is like G, except that for all i, the a i -source of G is no longer an a i -source in G . (If it was a b-source for some other source name b, it still remains a b-source.) The operation is only defined if G has a a i -source for each i. 2 • The merge operation, G 1 || G 2 , evaluates to a graph G that consists of all the nodes and edges in G 1 and G 2 . As a special case, if G 1 has an a-source u and G 2 has an a-source v, then u and v are mapped to the same node in G. This node then has all the adjacent edges of u and v in the original graphs.
By way of example, Fig. 4 shows the results of applying some of these operations to the s-graphs from Fig. 3. The first s-graph in the figure is Observe that this s-graph is exactly like G 3 , except that the "sleep" node is now a vcomp-source and not a root-source. We then merge G 1 with G 3 , obtaining the s-graph G 1 || G 3 . In this s-graph, the vcomp-sources of G 1 and G 3 have been fused with each other; therefore, the ARG1-edge out of the "want" node (from G 1 ) points to a node with label "sleep" (which comes from G 3 ). At the same time, the subj-sources of the two graphs were also fused. As a consequence, the ARG0 edge of the "want" node (from G 1 ) and the ARG0 edge of the "sleep" node (from G 3 ) point to the same node.
Next, we decide that we do not want to add further edges to the "sleep" node. We can therefore forget that it is a source. The result is the s-graph G 1 = f vcomp (G 1 || G 3 ). Finally, we can merge G 1 with G 2 [subj], and forget the subj-source, to obtain the final graph in Fig. 4. This s-graph could serve, for instance, as the semantic representation of the sentence "the boy wants to sleep".

Semantic construction with s-graph grammars
We will now demonstrate the use of s-graph grammars as a grammar formalism for semantic construction. We will first present a grammar that illustrates how functors, including control and raising verbs, combine with their complements. We will then discuss a second grammar which illustrates modification and coordination.

Complements
Consider first the grammar in Fig. 5. This is an s-graph grammar that consists of an RTG with start symbol S whose rules are shown in the left column, along with a string and a graph interpretation. The right column indicates the values of the homomorphisms h s and h g on the terminal symbols of the RTG rules; for instance, h g (comb subj) = f subj (x 2 || x 1 [subj]).
As a first example, let us use this grammar to derive a semantic representation for "the boy sleeps", as shown in Fig. 6. We first use the RTG to generate a derivation tree t, shown at the center of the figure. Using the homomorphism h s , this derivation tree projects to the term h s (t) (shown on the left), which evaluates to the string "the boy sleeps" in the string algebra. At the same time, the homomorphism h g projects the derivation tree to the term h g (t), which evaluates to the s-graph shown on the far right. Observe that the "boy" node becomes the ARG0-child of the "sleep" node by renaming the root-source of G 2 to subj; when the two graphs are merged, this node is then identified with the subj-source of G 3 . These operations are packaged together in the homomorphism term h g (comb subj).
The grammar in Fig. 5 can also analyze sentences involving control verbs. Fig. 7 shows a derivation of the sentence "the boy wants to sleep". We can use the same rule for "sleep" as before, but now we use it as the VP argument of want 1 . The grammar takes care to ensure that all s-graphs that can be s-graph h g (t) Figure 6: A derivation for "the boy sleeps", using the grammar in Fig. 5.
Figure 7: A derivation of "the boy wants to sleep" using the grammar in Fig. 5.
derived from VP have a subj-source along with the root-source that all derivable s-graphs have. Before we merge G 1 and G 3 , we rename the root-source to vcomp to fill that argument position. By leaving the subj-source of G 3 as is, the merge operation fuses the subj-arguments of "sleep" and "wants", yielding the s-graph G 1 from Fig. 4. Notice that we did not explicitly specify the control behavior in the grammar rule; we just "let it happen" through judicious management of argument names. The grammar also has a second rule for "wants", representing its use as a raising verb. The rule passes its grammatical object to its verb complement, where it is made to fill the subject role by renaming subj to obj. We omit the detailed derivation for lack of space, but only note that this rule allows us to derive AMRs like the one on the left of Fig. 1.

Modifiers
We now turn to an analysis of modification. The AMR-bank models modification with modification edges pointing from the modifier to the modifiee. This can be easily represented in an s-graph grammar by merging multiple root-sources without renaming them first.
We illustrate this using the grammar in Fig. 8. In the grammar we use shorthand notation to specify elementary s-graphs. For instance, the rule for coord merges its (renamed) arguments with an s-graph with three nodes, one of which is a root-source with label and and the other two are unlabeled sources for the source names 1 and 2, respectively; and with edges labeled op1 and op2 connecting these sources.
In the examples below, we abbreviate this graph as G coord ; similarly, G snore and G sometimes are the elementary s-graphs in the "snores" and "sometimes" rules.
Consider the derivation in Fig. 9, which is for the sentence "the boy who sleeps snores" using the s-graph grammar from Fig. 8. The subtree of the derivation starting at "rc" represents the meaning of the RTG rule homomorphisms NP → mod rc(NP, RC) s: relative clause. It combines the s-graph for "sleep" from the grammar in Fig. 5 with the s-graph for the relative pronoun, which is just a single unlabeled node, using the ordinary renaming of the root-node of the relative pronoun to subj. However, the rule for the relative clause then differs from the ordinary rule for combining subjects with VPs by forgetting the root-source of the verb and renaming subj to root. This yields the s-graph "sleep ARG0 − −−− → root ". The "mod rc" rule combines this with the s-graph for "the boy" by simply merging them together, yielding "sleep ARG0 − −−− → boy root ". Finally this s-graph is combined as a subject with "snores" using the ordinary subject-VP rule from earlier.
This derivation illustrates the crucial difference between complements and adjuncts in the AMR-Bank. To combine a head with its complements, an s-graph grammar will rename the roots of the complements to their respective argument positions, and then forget these argument names because the complements have been filled. By contrast, the grammar assumes that each s-graph for an adjunct has a root-source that represents the place where the adjunct expects the modifiee to be inserted. Adjuncts can then be combined with the heads they modify by a simple merge, without any renaming or forgetting.
One challenge in modeling modification is in the way it interacts with coordination. In a sentence like "the boy sleeps and sometimes snores", one wants to derive a semantic representation in which the boy is the agent of both "sleeps" and "snores", but "sometimes" only modifies "snores" and not "sleeps". Fig. 10 shows how to do this with the grammar in Fig. 8. The subtree below "sometimes" (which projects to the string "sometimes snores" on the string interpretation) is interpreted as the s-graph "snore root time − −− → sometimes". This is because the grammar rule for "sometimes" simply adds an outgoing "time" edge to the root-source of its argument, and leaves all sources in place. The coordination rule then combines this s-graph with G 3 from Fig. 3. This rule renames the root-sources of these two s-graphs to 1 and 2 respectively, but does not change their subj-sources. Thus these are merged together, so an ordinary application of the subject rule yields the s-graph shown at the right of Fig. 10.

Formal aspects
We conclude the paper by discussing a number of formal aspects of s-graph grammars.
First of all, this paper has focused on illustrating s-graph grammars using hand-written toy grammars for a number of semantic phenomena. We believe that s-graph grammars are indeed a linguistically natural grammar formalism for doing this, but ultimately one obviously wants to exploit the recent availability of meaning-banks to automatically induce and train statistical grammars. It is straightforward to make IRTGs a statistical grammar formalism, and to adapt algorithms for maximum likelihood and EM estimation, Viterbi parsing, etc. to statistical IRTGs (see Koller and Kuhlmann (2011) s-graph h g (t) Figure 9: A derivation for "the boy who sleeps snores" using the grammar in Fig. 8.
PCFG-style probability model and Chiang (2003) for a discriminative probability model that transfers easily to IRTGs). We have focused here on using s-graph grammars for semantic construction, i.e. as devices that map from strings to graphs. Algorithmically, this means we want to compute a parse chart from the string, extract the best derivation tree from it, and then compute its value in the graph interpretation. However, it is sometimes also useful to take a graph as the input, e.g. in an NLG or machine translation scenario, where one wants to compute a string from the graph.
We can adapt the IRTG parsing algorithm of Koller and Kuhlmann (2011) to graph parsing by showing how to compute decomposition grammars for the HR algebra. A decomposition grammar for an input object a is an RTG whose language is the set of all terms over the algebra that evaluate to a. We do not have the space to show this here, but the time complexity of computing decomposition grammars in the HR algebra is O((n · 3 d ) s · ds), where n is the number of nodes in the graph, d is the maximum degree of the nodes in the graph, and s is the number of sources that are used in the grammar. This is also the overall parsing complexity of the graph parsing problem with s-graph grammars.
There is a close formal connection between s-graph grammars and Hyperedge Replacement Grammars (HRGs), which we reviewed in Section 2. Every HRG can be translated into an equivalent s-graph grammar; this follows from the known encoding of HRG languages as equational sets over the HR algebra, see e.g. Section 4.1 of Courcelle and Engelfriet (2012). More concretely, one can adapt the treedecomposition construction of Chiang et al. (2013) to encode each HRG whose rules have maximum treewidth k into an equivalent s-graph grammar with s = k + 1 sources. Thus the parsing complexity of s-graph grammars coincides with Chiang et al.'s parsing complexity for HRGs of O((n·3 d ) k+1 ·d(k+1)).
One key difference between HRGs and s-graph grammars is that the "sources" that arise in the translation of HRGs to IRTGs are meaningless, abstract names, which are forgotten after each rule application. By contrast, s-graph grammars can use linguistically meaningful source names which can persist if they are not explicitly forgotten in a rule. By managing the lifecycle of the subj-sources explicitly, we were able to write succinct rules for control verbs in Section 4.1. Similarly, the coordination rule in Section 4.2 fuses whatever sources the coordinated elements have, and thus it can be applied verbatim to other syntactic categories beyond VP. This reflects Copestake et al.'s (2001) observation that the use of explicit argument names can support more general semantic construction rules than are available when arguments are identified through their position in an argument list (as e.g. in HRG).

Conclusion
We have introduced s-graph grammars, a synchronous grammar formalism that describes relations between strings and graphs. We have also shown how this formalism can be used, in a linguistically principled way, for graph-based compositional semantic construction. In this way, we hope to help bridge the gap between linguistically motivated semantic construction and data-driven semantic parsing. This paper has focused on developing grammars for semantic construction by hand. In future work, we will explore the use of s-graph grammars in statistical semantic parsing and grammar induction. A more detailed analysis of the consequences of the choice between argument names and argument positions in semantic construction is also an interesting question for future research.