We introduce a data-driven approach to generating derivation trees from meaning representation graphs with probabilistic synchronous hyperedge replacement grammar (PSHRG). SHRG has been used to produce meaning representation graphs from texts and syntax trees, but little is known about its viability on the reverse. In particular, we experiment on Dependency Minimal Recursion Semantics (DMRS) and adapt PSHRG as a formalism that approximates the semantic composition of DMRS graphs and simultaneously recovers the derivations that license the DMRS graphs. Consistent results are obtained as evaluated on a collection of annotated corpora. This work reveals the ability of PSHRG in formalizing a syntax semantics interface, modelling compositional graph-to-tree translations, and channelling explainability to surface realization. General graph-based meaning representations (MRs) that model sentence-level semantics aim to provide interpretable intermediate representations that are applicationand domain-independent (Koller et al., 2019). Recently, graph grammars and algebras that formalize semantic constructions were introduced to MR processing (for example: (Koller, 2015; Drewes and Jonsson, 2017; Groschwitz et al., 2017; Chen et al., 2018; Groschwitz et al., 2018; Lindemann et al., 2019; Donatelli et al., 2019; Chen and Sun, 2020)). These formal grammars bridge between linguistic assumptions and data-driven parsing, and offer the benefit of cross-framework adaptability. For instance, the ApplyModify algebra was adopted in parsing across 5 MR frameworks (Oepen et al., 2019) (Lindemann et al., 2019; Donatelli et al., 2019). Another formalism that was adopted in generating semantic graphs from syntax trees is synchronous hyperedge replacement grammar (SHRG) (Peng et al., 2015; Chen et al., 2018; Chen and Sun, 2020). The use of SHRG in recovering syntax trees from MRs has however received scant research coverage. Empirical results of PSHRG's application are limited to Jones et al. (2012)'s work in semantic-based machine translation. An immediate application of MR-to-tree parsing is surface realization. Previous data-driven approaches to it include rule-based (Flanigan et al., 2016; Song et al., 2017; Horvat, 2017; Ye et al., 2018) and neural methods (Song et al., 2018; Damonte and Cohen, 2019; Hajdik et al., 2019). All these methods do not generate syntactic analyses. In contrast, the Answer Constraint Engine (ACE; Carroll et al., 1999; Carroll and Oepen, 2005; Velldal and Oepen, 2006), an HPSG grammar-based parser, generates both derivations and sentences from Minimal Recursion Semantics (MRS; Copestake et al., 2005). If we can induce an SHRG from data, MRs can be translated into derivation trees without relying on a hand-engineered grammar, and natural language texts can be obtained by realizing the terminals. Combining the strengths of rule-based systems and the data-driven paradigm, such an approach gives both linguistically-informed realization processes and explainable results, removes syntactic ambiguities that would otherwise exist in flattened surface strings, and provides potential usage for downstream tasks such as chunking. Among the different MR frameworks, we investigate Dependency Minimal Recursion Semantics (DMRS; Copestake, 2009). DMRS are directed graphs derived losslessly from MRS, whereas an MRS structure with respect to a reading of an English sentence is composed along with a derivation tree using the English Resource Grammar (ERG; Flickinger, 2000, 2011), a broad-coverage hand-engineered HPSG grammar of English. DMRS encodes logical formulae with underspecified scopes (for an introduction, see: Copestake, 2009). Fig. 1 shows an example of an ERG analysis. mantic algebra on the constructions of MRS, where the introduced constraints allow the semantics of complex sentences to be derived from simple composition rules. The compositionality exhibited in the MRS (for a discussion, see: Bender et al., 2015) is not obvious in some other MRs, e.g., Abstract Meaning Representation (AMR; Banarescu et al., 2013) (Bender et al., 2015), and we suggest that HRG be particularly suitable to simulate the DMRS algebra if equipped with adequate adaptations. In this paper, we shed light on the applicability of a succinct grammar formalism in approximating the semantic compositions of a graph-based MR. Essentially, we capture the syntaxsemantics interface of the ERG by inducing a PSHRG from an annotated treebank to provide generative models for both DMRS graphs and derivation trees. With the induced PSHRG, derivation trees that license the DMRS graphs can be reconstructed through graph parsing. We describe the procedures and the relevant adaptations involved, from PSHRG induction, parsing to generating derivation trees. Finally, we present the empirical results on derivation trees and surface strings reconstruction from DMRS graphs under different configurations. Hyperedge replacement grammar (HRG) is a context-free rewriting formalism for generating graphs (Drewes et al., 1997). A synchronous HRG (SHRG) defines mappings between languages of graphs, which in our context are an HRG and a context-free grammar (CFG) for strings. We give the definitions in this section. Hypergraph and Hypergraph Fragments. A hypergraph is specified by a tuple  =  , ,   , where  is a finite set of nodes,    + is a finite set of hyperedges, each of which connects one or more distinct nodes,  :    assigns a label from the finite set  to each hyperedge. A hypergraph fragment is a tuple  =  , , ,   , where  , ,   is a hypergraph and    + is an ordered list of distinct nodes called the external nodes. HRG. An HRG is a tuple  =  , , ,   , where  and  are disjoint finite sets of nonterminal and terminal symbols respectively,  is a 5426 finite set of productions of the form    , where    and  is a hypergraph fragment where hyperedge labels are over    , and    is the start symbol. In a step of rewriting a hyperedge  by a production    ,  is replaced with a copy of  by identifying each of the nodes connected by  with a distinct external node of  , whose mapping is specified in the production. Fig. 2 illustrates the HRG rewriting process. Synchronous HRG. An SHRG is a tuple  =  , ,   , ,   , where  is a finite set of nonterminal symbols in both the CFG and the HRG,  and   are finite sets of terminal symbols in HRG and CFG respectively,    is the start symbol, and  is a finite set of productions of the form    ,   ,  , where  is a hypergraph fragment with hyperedge labels over    ,   is a symbol sequence over     , and  is a bijection between the nonterminal hyperedges of the same labels in  and   . When applying a production    ,   ,  ,    rewrites the graph as described in the HRG and the synchronous operation on the CFG counterpart is a string rewrite by     (see Fig. 3). Probabilistic SHRG. A probabilistic SHRG is obtained by assigning a constant probability to each production in the SHRG, where probabilities of the productions that rewrite the same nonterminal add up to one. In this work, the probability of    ,   ,  is simply modelled as the fraction of times it appears among all    in the training data. The probability of a derivation is the product of the probabilities of the context-free SHRG productions applied. In this section, we describe how a PSHRG is induced from training data and how a derivation tree is reconstructed from a DMRS of the test data with the induced grammar. We also describe two methods for modelling the semantics of lexical items. DMRS as Hypergraph. We first establish the connections between DMRS and HRG. A DMRS graph is modelled as a hypergraph  with terminal hyperedges. In  , each terminal hyperedge corresponds to a DMRS node or edge: the former can connect to an arbitrary number of nodes in  , and the latter connects to only two nodes in  . We describe how to induce a PSHRG from pairs of aligned trees and graphs. The PSHRG induction procedure generally follows Chen et al. (2018)'s SHRG extraction algorithm, which operates based on the surface string alignment information between DMRS graphs and their derivation trees (for expositions, see: Chen et al., 2018). Fig. 3 illustrates the grammar induction process. For each nonterminal in the tree, i.e., a node labelled by an ERG syntactic construction (a label of the form *_c , e.g., hd-cmp_u_c ), a production    ,   ,  is extracted, where  ,  and   are the ERG syntactic construction, connected DMRS hypergraph fragment and daughter ERG rule(s) respectively. For a binary ERG construction, if any of its daughters is a semantically empty terminal (e.g., for the lower hd-cmp_u_c in Fig. 3), no productions are extracted (discussed in 3.3.3). The DMRS hypergraph fragment specified by  is then rewritten to a 5427 nonterminal hyperedge labelled by  . We perform the same rule extraction procedure for each training instance to induce an SHRG from the training data, thus a PSHRG when we consider the frequency information. To recover the derivation tree of a DMRS, we can translate the semantic compositions to the corresponding syntactic operations by parsing the DMRS with the induced PSHRG (see Fig. 3). We aim at recognizing the best derivation according to a PSHRG model, which requires exact graph parsing. Chiang et al. (2013); Groschwitz et al. (2015); Ye and Sun (2020) studied HRG parsing and proposed various techniques on improving the efficiency, but no evaluation on accuracy is performed on the parsed results with respect to a gold-standard grammar. Although efficient algorithms are developed for HRG parsing, existing parsers do not provide convenient adaptations to the extensions introduced in this work. Rather than efficiency, our work focuses on the correctness of derivations as measured against the original derivations that license each DMRS. Therefore, we implement a parser that returns the best PSHRG derivation of DMRS via bottomup passive chart parsing (for details of the parsing algorithms, see Appendix A). We introduce two adaptations to align PSHRG with the semantics introduced by the ERG lexical items. Complex semantics. While most lexical items introduce just one DMRS predicate each, some introduce more complex semantics. As an example, Fig. 4 shows that somebody provides both the _some_q quantifier and the person predicate. Therefore, the R.H.S. hypergraph fragment of an SHRG production is not confined to a hypergraph fragment with one or two terminal hyperedges, but one with more than two terminal hyperedges that corresponds to a connected DMRS subgraph. Empty semantics. There are semantically empty lexical items that do not contribute predicates to the DMRS, e.g., auxiliary verbs and particles. This poses another challenge for derivation reconstruction because the syntactic properties of these lexical items are highly language-dependent, yet they are not captured by general semantic representations as they are not semantically functional. To recognize complex semantics, we borrow the idea of the graph canonization method described by Horvat (2017) that isomorphic DMRS subgraphs can be identified by comparing if their canonical representations are the same. Graph canonization is achieved in two steps: first, each node in the DMRS subgraph is given a canonical node representation by encoding its 1and 2-hop neighbours; then the final canonical form is obtained by concatenating the sorted node representations based on a canonical ordering. Most subgraphs introduced contain fewer than seven DMRS nodes, for which the canonization method is sound (Horvat, 2017). Fig. 4 exemplifies the idea. During grammar induction, the canonical forms of all small subgraphs that correspond to ERG lexical items are extracted from the training data. Then, given a DMRS from the test data, we first identify its subgraphs that are isomorphic to any of the extracted ones before parsing. This is achieved by first enumerating all small subgraphs from the DMRS, then computing the canonical form for each of them, and finally comparing the canonical forms with those of the subgraphs extracted. The process can be sped up by computing the canonical form of a subgraph only if its collection of DMRS predicates is present in the set of those extracted from the training data. We devise a semi-automatic method to extract (dur-ing grammar induction) and recover (during parsing) the syntax of common semantically empty words. To this set of words with empty seman-5428 tics, we define a collection of linguistic signals that can serve as their cues, and match each signal to the set of lexical items it can recover. For example, the tense and aspects of verbs and predicative adjectives are signals for auxiliary verbs. During SHRG induction, the signals are first identified from the DMRS node attributes and are then generally passed up from the syntactic head daughter. When extracting a binary construction, if the unextracted subtree (described in 3.1) contains a semantically empty lexical item that matches a signal of any of the daughters, a hypergraph fragment is extracted together with the subtree associated with that signal. During parsing, the same bottomup signal passing procedures apply. If the R.H.S. hypergraph fragment of a binary production is recognized and any signal passed up matches that of an extracted subtree, the HRG production is applied and the CFG subtree is added on top of the two daughters in the derivation tree (see Fig. 3). To approximate complex grammars or implicit relations established between trees and graphs by PSHRG, we introduce extensions for improving on both the precision and generalizability of modelling. The application of most of the proposed techniques is not limited to the DMRS, but to general MR parsing by PSHRG. Three techniques are introduced to impose restrictions to semantic compositions, allow probability to be estimated on more fine-grained SHRG productions, and prevent overgeneration. Typed HRG. Chen and Sun (2020) introduced typed HRG, where each node of a hypergraph (frag-ment) and hyperedge is assigned a label chosen from a finite set. In typed HRG, an R.H.S. hypergraph fragment is recognized only if the type of its every node matches that of the corresponding node in the input graph. In our case, we propose to type a node by the major sense tag of the corresponding DMRS predicate. For example, in Fig. 5, the nodes on the R.H.S. correspond to _want_v_1 and _go_v_1 respectively, so both are typed v . An HPSG derivation tree merely records the recipe of a derivation, where the non-atomic rule symbols hd-optcmp_c ^hd-cmp_u_c [VP] hd-optcmp_c ^hd-cmp_u_c [VP] _*_v_*  ARG2/H H3'  _*_v_* to_c_prop C3' hd-cmp_u_c ^sb-hd_mc_c [S] 2 1 hd-cmp_u_c ^sb-hd_mc_c [S] v 1 2 v v v Figure 5: P3 in Fig. 3 with annotated syntactic constructions, typed nodes and a delexicalized DMRS predicate. only convey highly generalized linguistic principles. Each rule represents a unification of typed feature structures. Inspired by Zhang and Krieger (2011), we annotate each syntactic construction with that of their immediate parent (order-2 vertical markovization) and the syntactic category of the phrase (see Fig. 5). This adds extra contextual information to the constituents. We further normalize the derivations by substituting chains of unary lexical rules, affixation rules for punctuation marks, and the preterminals by the canonical form of a DMRS node or subgraph (see Fig. 4). Framework-Specific Constraints. PSHRG Parsing on DMRS without regard for the MRS semantic algebra leads to inefficiency and overgeneration. In particular, the features INDEX and LTOP in MRS specify the semantic materials of a phrase that are accessible during composition. In the ERG, their values are determined by the type of composition. 1 Hence, when parsing a DMRS, every composition should ensure that subsequent compositions can only happen to the two variables of the newly composed item. This procedure resembles Carroll and Oepen (2005)'s proposal on index accessibility filtering. The checks can be easily incorporated into SHRG parsing (for the details, see Appendix B). Nevertheless, INDEX and LTOP are not the only features that permit compositions in the ERG. Therefore, the constraints introduced prevent overgener-ation to a large extent but lead to undergeneration. In this work, we examine the two most prominent features, and how we should further integrate the MRS algebra to HRG is an open question. Two underspecification methods are developed to alleviate the rule sparsity and out-of-vocabulary (OOV) problems, which are the main challenges faced by general rule-based systems. 1 The precise algebras of the two features in the ERG are not discussed fully here. In brief, the INDEX and the LTOP usually come from the syntactic head, but come from a scopal modifier if the semantic composition is scopal. For expositions, see: Copestake et al. (2001); Copestake (2009). Extended HRG Productions. When recognizing an HRG production    on a hypergraph  , we suggest that the external nodes of  be not distinguished from the non-external nodes. Consequently, the rewriting hyperedge  connects to a variable number of nodes, and such number depends on  . To motivate such decision, consider H1 of Fig. 3. The fact that the hyperedge _boy_n_1 connects to an external node is not significant to the characterization of the sp-hd_n_c (the specifier head construction where the specifier is the semantic head). This effectively creates more SHRG productions that share the same probabilities if their R.H.S. hypergraphs (minus external nodes) are identical. Delexicalization. The PSHRG models are estimated based on delexicalized productions: the lexeme stems of verbs, adjectives, adverbs, and nouns (whose DMRS predicates are in the form of  _*_v_* ',  _*_a_* ' and  _*_n_* ' respectively) are underspecified (see Fig. 5). This is a significant distinction between our grammar and the ERG since the ERG is highly lexicalized. 2 Hence, delexicalization trades lexical preciseness for OOV coverage. Furthermore, since an approximation grammar is assumed to have no access to the lexical information of the underlying grammar, the results of our experiments would reflect the viability of PSHRG as a general approach to grammar approximation. The main objective of the experiments is to assess the performance of PSHRG models on simulating DMRS compositions and producing approximating derivation trees. Specifically, we reconstruct a derivation tree for each DMRS whose nonterminals are aligned to DMRS subgraphs and labelled by an ERG syntactic construction; the ERG 1214 contains more than 210 fine-grained syntactic constructions that reflect the distinguishing properties of different syntactic constructions. As a secondary evaluation, we analyze our performance on the task of surface realization. The purpose of this is twofold: first, assessing the quality of the surface strings produced from the recon-2 Each lexical entry in the ERG is assigned to exactly one lexical type, which determines most of its syntactic and semantic properties. For example, inform , advise and remind share a lexical type because they all select a noun phrase and a sentential complement. The detailed lexical types interact with the highly generalized linguistic principles to produce precise linguistic interpretations. structed derivation trees gives additional perspectives on the evaluation of our models; and secondly, there are existing works on surface realization from DMRS, so our models can be benchmarked against. Finally, we evaluate the significance of the two proposed adaptations, namely recovering words with empty semantics and incorporating framework-specific constraints to PSHRG parsing. An instance of sample input and sample output are provided in Appendix C. 5.1 Data The main data set we experiment on is the Ninth Growth of the Redwoods Treebank (Oepen et al., 2002). 3 It contains English sentences from a range of domains including Wall Street Journal (WSJ) and the Brown corpus, each paired with the analyses of the 1214 version of the ERG. Each MRS is converted into a DMRS using Pydelphin (Copes-take et al., 2016). 4 We discard the instances with ambiguous analysis, disconnected DMRS, and unparsable MRS by Pydelphin. To assess the scalability of our models, we further sampled sentences from the Gigaword v.5 corpus (Parker et al., 2011) for model training, where extra training instances are obtained by parsing sentences with the ACE and choosing the best ERG analysis for each sentence as ranked by the ACE. After preprocessing, the total number of instances in the training and test sets are 70,774 and 10,042 respectively under the standard Redwoods data split. 70,774 extra training instances are created from the Gigaword corpus. We removed the mostly uninformative syntactically covert quantifiers (e.g., udef_q , proper_q ) in all DMRS graphs. The numbers of DMRS nodes reported below are counted after the removal. Subgraph canonization (3.3.2) was performed only on the DMRS subgraphs of fewer than seven nodes. The maximum length of the unary chains in the generated derivation trees was set to be three. The parser was implemented in PyPy3.6 and ran under one Intel Xeon E5-2697 CPU on x86_64 Linux. Our implementation is available online. 5 3 http://svn.delph-in.net/erg/tags/ 1214/tsdb/gold 4 https://github.com/delph-in/pydelphin 5 https://github.com/aaronlolo326/ pshrgOnDMRS 5430 DerivationAnnotation Model ParsEval-Graph Coverage P R F 1 M1C SHRGPCFG 76.79 74.90 75.84 80.58% PSHRG 81.86 79.85 80.84 80.58% PSTHRG 83.81 81.23 82.50 74.31% M2C SHRGPCFG 83.13 80.44 81.77 68.69% PSHRG 84.52 81.60 83.03 68.69% PSTHRG 87.04 83.66 85.32 61.50% Table 1: Results on the accuracy of derivation reconstruction under standard Redwoods data split. If a DMRS is parsed correctly, the synchronously reconstructed derivation should not deviate too much from the original derivation. Nevertheless, equivalence is a sufficient, but not necessary condition for a parse to be correct since syntactic differences do not necessarily contribute to semantic differences. We devise a modified version of the ParsEval (Black et al., 1991) measure, ParsEval-Graph, to assess the quality of the generated trees, as the constituents of the trees are not aligned to a surface string but on the input semantics. In ParsEval-Graph, the alignment of a constituent refers to the DMRS nodes covered instead of the characters covered in the surface string. Following ParsEval, ParsEval-Graph only accounts for binary rules, and preterminals are disregarded. All ParsEval-Graph scores are evaluated on the parsable instances of the respective models on unannotated derivation trees. As introduced in 4.1, we experiment with the typed variant of PSHRG, PSTHRG, and two configurations of tree annotation, namely order-2 vertical markovization with syntactic category annotation (M2C), and only syntactic category annotation (M1C). Since no existing works on data-driven DMRS parsing or surface realization produce syntactic derivations, we develop a baseline model SHRGPCFG for benchmarking. SHRG PCFG parses a DMRS with the SHRG induced and the probability of each parse is given by a PCFG model where the probability of each CFG production     is modelled as the fraction of times     appears among all    in the training data. The ACE is not evaluated because it always generates derivations faithful to the ERG. and outperform the baseline under the same annotation configurations. More extensive annotation and typing the grammar respectively improve the F 1 score by about 2, at the expense of coverage reduction caused by rule sparsity when the Redwoods training set does not provide adequate data for the over-specific annotation. It is insightful to note that the baseline under M2C performs at a level between the PSHRG model and PSTHRG model on M1C, which conveys that the contextual information of a nonterminal node could already provide ample information on the semantic compositions. To study models' performance with respect to the size of the training data, we add the Gigaword instances on top of the Redwoods training set. This doubles the amount of training data. As reported in Table 2, the coverages of the two models increase by 4.50% and 6.31% respectively with more data. Nevertheless, the accuracy of derivations does not improve further, as frequency-based context-free probability models have low learning capacities. Despite all DMRS being generated by the ERG, the ACE does not parse every DMRSparsing fails when a DMRS predicate is OOV. In contrast, our models parse more instances than the ACE when given more training data, since they generalize to OOV with delexicalization. Although delexicalization removes much lexical information, we suggest that SHRG-based parsing and the incorporation of MRS-specific constraints can restrict compositions outside of the ERG to a large extent. To produce a surface string from a DMRS, we realize the most frequently recorded surface form for each preterminal from the reconstructed derivation tree. We compare our work with the Neural MRS (Hajdik et al., 2019) and the ACE. The Neural MRS generates in an end-to-end manner without intermediate syntactic derivations. For more comparable results, we evaluate the models under M1C annotation configuration since they have similar parse 5431 Model BLEU GenerateSyntacticStructures Redwoods WSJ Brown Neural MRS 66.11 65.78 45.00 No ACE (ERG) 62.21 -Yes PSHRG (M1C) 59.33 63.65 58.29 Yes PSTHRG (M1C) 60.67 64.77 59.47 Yes Table 3: Results on surface realization. We evaluate the generation quality with BLEU (Papineni et al., 2002) using SacreBLEU (Post, 2018) 6 . Following (Hajdik et al., 2019)'s evaluation on inand out-of-domain performances, we experiment on the different trainingtest data splits, namely the WSJWSJ and WSJBrown splits. WSJ contains 34,751 training instances and 1,442 test instances, and Brown contains 2,181 test instances. 7 All BLEU scores are evaluated on the parsable instances of the respective models. Table 3 shows that our models perform consistently across data splits. Under the Redwoods standard data split, our models are worse than the neural model. With similar parse coverages to the ACE, our performance is also close to the ACE. Under the WSJ-Brown split, our PSHRG models outperform the Neural MRS. 8 The PSHRG (M1C) parses 74.90% of the test set under the WSJWSJ split. When the model is typed and when switching from into out-of-domain, the models parse about 7% less data respectively. The coverages of M1C models reported here are lower than those in Table 1 since the amount of training data is halved. Therefore, we consider the relative decreases in coverage from into out-of-domain of our respective models to be more insightful on models' transferability between domains than the absolute coverage. Apart from the automatic evaluation, we also value qualitative details and seek linguistically interesting phenomena that result from a grammar-based approach. To this end, we observe that our models identify different realization possibilities from the original sentence to the same semantics 6 https://github.com/mjpost/sacreBLEU 7 The numbers of training and test instances of Neural MRS are slightly greater than ours after respective preprocessing. 8 To provide context on assessing our model under a fullcoverage scenario, we try to provide a naive fallback for the unparsable instances: For each of these instances, the partially realized non-overlapping constituents are concatenated in order of decreasing number of the DMRS nodes covered to form the final sentence. With this quick fix, our PSHRG (M1C) model attains a BLEU score of 51.08 on the WSJBrown split. Compared to neural approaches, PSHRG is a shallow statistical model with a high inductive bias. It encodes a syntaxsemantics interface effectively through treeand graphrewriting. Even though our models are not engineered towards the task of surface realization, and with limited morphological analyses and no language modelling, our approach is still competitive as evaluated quantitatively and qualitatively. We suggest that PSHRG-based approaches and neural models be decent alternatives to each other for general surface realization from MR: neural models provide full-coverage and high-quality generation when substantial training data is available, whereas PSHRG-based solutions extrapolate from limited data and in out-of-domain scenarios, and produce interpretable derivations. We conduct a few more experiments to test against the significance of two proposed adaptations, namely the solution to semantically empty words (3.3.3) and framework-specific constraints (4.1). We implement two models, PSTHRG (M1C) and PSTHRG (M1C), which parse DMRS without regard for semantically empty lexical items and MRS constraints respectively. As reported in Table 5, The treatment of empty semantics not only adds 15.51% more parsable instances but also corrects some parses in the 58.80% that require analyses of empty semantics, thus pro-5432 Model ParsEval-Graph BLEU Coverage P R F 1 PSTHRG (M1C) 83.81 81.23 82.50 60.67 74.31% PSTHRG (M1C) 84.68 81.09 82.85 54.07 58.80% Table 5: Results of ablation of inserting words with empty semantics under the Redwoods standard split. ducing more accurate surface strings. Fig. 6 shows the importance of MRS constraints on parsing efficiency. We set a time limit of 300 seconds on parsing, and the parsing of 16.71% of the WSJ test set exceeds the time limit. When the DMRS contains 24 or more nodes, timeouts occur on at least one DMRS graph of each size. Table 6 shows that when the constraints are enforced, all parses are completed in much shorter times and the derivations reconstructed are more accurate. The proposed frequency-based PSHRG models are simple yet competitive data-driven baselines for recovering derivations of DMRS. They can be further combined with sophisticated machine learning methods for a more accurate parse ranking. More extensive features can also be included to enhance grammar approximation. For instance, the feature-paths of ERG signs are shown to be helpful for PCFG approximation (Zhang and Krieger, 2011). Language-specific knowledge about words with empty semantics is also critical for syntactic purposes. In terms of efficiency, Ye and Sun (2020) showed that exact parsing can be very practical on Elementary Dependency Structures (EDS; Oepen and Lnning, 2006), a close equivalent to DMRS that excludes scopal information. Different from Ye and Sun (2020)'s implementation, we retain more than 210 ERG syntactic constructions for precision and adopt delexicalization for generalization, both of which increase the search space of parsing and trade efficiency. We suggest that the described PSHRG-based approach can be a potential alternative to the unification-based ACE generator for surface realization from DMRS, whilst improving parsing coverage, accuracy and efficiency without sacrificing one another would be a critical problem for future research. In this paper, we report our findings with respect to the engineering decisions we investigated based on the data at hand. In principle, the application of the described PSHRG-based approach is not limited to DMRS, but also to generic graph-to-tree translations that exhibit compositionality, if suitable data of aligned trees and graphs is available. If explicit associations do not exist between the trees and graphs, the induced grammar formalizes the underlying relations and patterns; otherwise, the induced grammar provides an approximation to such relations, which can be desirable for computation purposes. Based on the experimental results, we can assess the contributions of this work from three perspectives: (1) PSHRG with framework-specific adaptions as a formalism that approximates the semantic composition process of DMRS, (2) PSHRG graph parsing with framework-independent extensions as a general approach to modelling compositional graph-to-tree translation, and (3) derivation reconstruction with a PSHRG induced from data as a solution to surface realization from MRs that provides explainability, syntactic disambiguation, and syntactic variations. We hope that this work provides relevant and substantial empirical insights to stimulate more research on approaching MR processing with linguistically-motivated methods. The work was supported by grants from the Research Grant Council of the Hong Kong Special Administrative Region, China [Project No.: CUHK 14205618], and CUHK Direct Grant No. 4055159.
method abstain method abstain objective abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain result method abstain method result abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain method abstain abstain objective abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain method method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result method method abstain abstain abstain abstain abstain abstain abstain abstain method abstain other method abstain abstain abstain method method abstain abstain other abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain method result abstain abstain abstain other method other