Formal Semantics for Dependency Grammar (2023)

Abstract: In this paper, we provide an explicit interface to formal semantics for Dependency Grammar, based on Glue Semantics. Glue Semantics has mostly been developed in the context of Lexical Functional Grammar, which shares two crucial assumptions with Dependency Grammar: lexical integrity and allowance of nonbinary-branching syntactic structure. We show how Glue can be adapted to the Dependency Grammar setting and provide sample semantic analyses of quantifier scope, control infinitives and relative clauses.

## introduction although the name dependency grammar suggests a theory covering everything that could reasonably be understood as grammar (often, these days, phonology, morphology, syntax and semantics), it is fair to say that the focus has to a large extent been on syntax. nevertheless, there have been some attempts to extend the idea to phonology (e.g. dresher and van der hulst 1998) and semantics (e.g. the tectogrammatical layer of functional generative description: @xcite . in section 2, we argue that such frameworks lack some important desiderata of semantic theories and suggest that it is reasonable for dependency grammar to remain agnostic about semantics and instead attempt to build an interface between dependency syntax and established semantic theories. the main contribution of the paper is to provide such an interface to one influential semantic theory, compositional (also known as formal or logical) semantics in the tradition going back to frege. we take inspiration from the implementation described in @xcite , but the focus here is on how glue semantics can provide a general interface to semantics for dependency grammar, irrespective of this concrete implementation that is tied to a particular meaning language (partial cdrt, haug 2014) and a particular version of dependency grammar (universal dependencies, de marneffe et al. 2021), which deviates from most theoretical versions of dependency grammar in various respects. in section 3 we briefly introduce compositional semantics and the constraints it puts on the interface to syntax. then we introduce glue semantics as a way of satisfying those constraints in section 4. finally, in section 5 we show how glue semantics can be applied to dependency syntax. section 6 concludes. ## previous work the fundamental concept of dependency grammar is of course dependencies. but these are in themselves nothing but asymmetric, binary relations as we find them in many domains. for example, a phrase structure tree can be defined in terms of two such relations, dominance and precedence. the characteristic feature of dependency syntax is therefore not just that it is based on dependencies, but that those dependencies are taken to hold between words. 1 this can be seen as a strong version of the lexical integrity hypothesis @xcite : not only are words atomic with respect to syntax, but they are the only atoms of syntax. one intuitive way to extend dependency syntax to semantics, therefore, is to find an analogue to words on which to build semantic graphs. indeed, @xcite provide a useful classification of graph-based semantic representations by the degree to which the nodes of the graph are anchored in the words of the sentence: some representations, such as ccg word-word dependencies @xcite , just use the words as nodes; others, such as prague tectogrammatical graphs @xcite ) allow for a looser correspondence where nodes can also rep-resent elided material (e.g. pro-drop, ellipsis), or copied material (e.g. words that are interpreted twice in a coordination structure); and yet others, most prominently abstract meaning representations @xcite are fully unanchored: there is no explicit correspondence between words and nodes. while such frameworks have shown themselves useful for various computational tasks, including natural language inference, we argue that they currently lack two features that a semantic theory should have: compositionality and an explicit proof theory. by compositionality we mean that, given a representation of the syntax (in our case, a dependency graph) and of the lexical items in the sentence, it should be possible to enumerate the possible semantic representations of the sentence. this is a weak notion of compositionality: we do not require that there are interpretations of parts of the dependency graph, nor that syntax and lexicon determine a unique meaning, only that there is some form of systematicity in the mapping between complete syntactic and semantic representations. notice that this is a theoretical desideratum rather than a practical one: given a large dataset of hand-annotated semantic representations, it might make more sense to train a semantic parser directly rather than going via syntax, and this is in fact a common approach in natural language inference these days. nevertheless it is clear that if we want to construct a semantic theory for dependency grammar, the semantic representations must be constrained by the syntactic representations we assume if the theory is to have any empirical bite. and yet not all graphbased semantic theories have this: abstract meaning representation, for example, is hand-annotated without regard to any particular syntactic representation. while this does not make it less useful, it does make it hard to use as a semantic theory for dependency grammar. the prague tectogrammatical layer, on the other hand, is a graph-based semantic representation that is explicitly linked to a surface dependency syntax representation, the analytical layer. similarly, meaning-text theory develops an interface between syntax and a graphbased semantic representation (see @xcite for an introduction). by explicit proof theory, we mean that the semantic representations must be able to answer questions like "if a set of sentences p is true, does it follow that sentence h is true?". we take the ability to answer such questions to be a core property of human reasoning. again, this is a theoretical desideratum: in natural language inference tasks, we are typically only given a few explicit sentences p 1 , p 2 from p , whereas an inference to h relies on implicit propositions p 3 , . . . , p n , which could be either just world knowledge or somehow be made salient/likely by the explicit premises p 1 , p 2 . in this situation, rather than trying to enumerate the possible background knowledge on which an inference may draw, it may easier to predict directly whether p 1 and p 2 make h likely. but this cannot be the basis for a semantic theory. we are not aware of any graph-based semantic frameworks that provide a sound and complete inference system for computing entailments, though some come close. graphical knowledge representation @xcite explicitly views "graphs as firstclass semantic objects that should be directly manipulated in reasoning and other forms of semantic processing". the semantic graphs of meaning-text theory are more directed towards tasks like paraphrasing rather than logical deduction, but @xcite explores the connection to logic. indeed, basing semantic representations on logic is one straightforward way to provide a proof theory. this is a long tradition reflected in many theories such as montague's intensional logic @xcite , discourse representation theory @xcite and minimal recursion semantics @xcite . linking dependency syntax to this line of work therefore provides the advantage of being able to connect to a large body of semantic work. but to do this, we must solve the compositionality problem: how do we systematically build formulae in some logic-based formalism from a dependency graph? to our knowledge, dependency tree semantics @xcite was the first attempt to provide such an interface between dependency syntax and formal semantics. however, robaldo only deals with quantifiers and quantifier scope ambiguity, and it is not obvious how to generalize his work to other phenomena. the aim of this paper, then, is to provide a general solution to the compositionality problem which would allow dependency syntacticians to connect their syntactic analyses to existing work in formal semantics, or indeed to develop their own semantic analyses in parallel with syntax. ## formal semantics and the syntax-semantics interface as we pointed out above, basing semantic theory on logic provides an immediate proof theory. indeed, the very development of formal logic from aristotle onwards can be seen as a way to provide a proof theory for natural language. the real problem, then, is compositionality: how do we systematically constrain the logical formulae that are licit translations of a given natural language sentence? one influential way to achieve this is to provide meanings for lexical items and let the syntactic structure of the sentence guide how we assemble them into a meaning for the whole. this is known as frege's principle of compositionality (although it is not clear that frege endorsed it in this form): the meaning of a (syntactically complex) whole is a function only of the meanings of its (syntactic) parts together with the manner in which these parts were combined. this is a much stronger notion of compositionality than what we saw in section 2, but it has guided much previous work in formal semantics. one immediate problem is that it is not always clear what the meanings of the parts should be. for example, it seems intuitive that the meaning of every man loves chris is something like ∀x.man(x) → love(x, c). here it seems obvious that the verb loves contributes the predicate love, the word man contributes the predicate man, and the name chris provides the constant c; but that then leaves the determiner every to contribute the rest of the meaning, i.e. the quantifier ∀x and the ocurrences of x that it binds, as well as the implication →, although these parts are scattered around in the sentence in a way which makes it unclear how we can provide a systematic procedure for combining the meanings. yet @xcite insight was that the lambda calculus can provide such a systematic procedure. intuitively, the scattered meaning of every can be represented as ∀x.? →?, where the two question marks represent predicates containing x. in the lambda calculus we can represent this as λp.λq.∀x.p (x) → q(x). this means that every is a function that takes two predicates and says that for any x, if the first predicate (the noun p that every combines with) applies, then the second predicate (the verb that every p is an argument of) also applies. montague's system based on the lambda calcu-lus achieves compositionality, but it imposes strong constraints on the syntax-semantics interface that are problematic from the point of view of dependency grammar. first, the homomorphism problem: compositionality in the strict sense requires that syntax and lexicon jointly determine meaning: meaning differences between two sentences must be attributed either to the parts of the sentences (i.e. the lexicon), or the manner in which they are combined (i.e., the syntax). therefore, if a sentence with no ambiguous words is semantically ambiguous, that difference must necessarily be reflected in the syntax. this is the case, for example, with different quantifier scopings. more generally, homomorphism requires that the syntactic tree is strictly binary branching, which is typically not the case in dependency structures. for example, the lambda calculus requires that a verb combine with its subject and object in a particular order (it must combine with one before the other), whereas dependency grammars typically assume no hierarchical difference between subject and object, with both being sister nodes under the verb. one way to go would be to use the syntactic function to distinguish the two, for example by replicating the view of most phrase structure grammars that the object bears a closer relation to the verb than the subject. this is the approach taken in udeplambda @xcite , where a syntactic function hierarchy is used to binarize the dependency tree before it is fed to the composition process. but given that many languages exhibit subject-object scope ambiguities, it makes more sense to interpret the flat dependency tree as an underspecified representation, which entails giving up on the view that syntax and lexicon determine meaning. second, lexical integrity is another problem. it is often natural that single lexical items provide two or more different meanings that do not directly combine with each other, but interact with other elements of the sentence in complex ways. for example, the verb introduces the basic predicateargument structure, but in many languages also temporal and modal meanings, and we cannot necessarily just combine these first: modal meanings, for example, may need to take scope over the arguments of the verb. if these composition patterns are to be directly determined by the syntax, we need to assume abstract syntactic heads for modality, tense etc. this is indeed often done in chomskyan approaches, but is alien to dependency syntax, which normally assumes lexical integrity, i.e. that words are the atoms of the syntactic structure. in sum, "standard" formal semantics in the tradition after montague relies on strictly binary syntax and syntactic decomposition of lexical items. this makes it hard to adapt to dependency grammar. but fortunately these problems have been tackled within the tradition of another lexicalist theory of syntax that also does not enforce binary syntax, namely lexical functional grammar @xcite , via the theory of the syntax-semantics interface called glue semantics (glue: @xcite . ## basic glue semantics the semantic building blocks in glue are called meaning constructors; these are expressions consisting of two parts: a meaning, given in the lambda calculus over some formal language; and a formula of another logic, so-called linear logic @xcite , which constrains but does not necessarily uniquely determine the valid patterns of combination between meaning constructors. semantic composition is logical deduction, driven by the linear logic parts of meaning constructors. before we get into the technical details of how this works, let us consider how it helps with the problems just described. treating semantic composition as logical deduction helps to loosen the conection between meaning composition and syntax: provided the logic we use has the property of commutativity, then the order in which we combine meanings is driven wholly by the types of the meanings themselves, and not by the order the words they correspond to happen to occur in the string. since we therefore no longer require the syntax itself to impose a strict order of combination, it also frees us from the obligation to limit our syntactic trees to binary branching ones. finally, it means that semantic ambiguities, such as scope ambiguities, need not correspond to syntactic ambiguities: since the order of combination in syntax and semantics can vary independently, there can be semantic ambiguities which have no syntactic correlate. we will present an explicit example of how this works shortly. linear logic is chosen as the logic of semantic combination because it has the property of resource sensitivity: premises cannot be reused or discarded in linear logic, unlike in classical logic. this is because linear logic lacks the structural rules of weakening and contraction @xcite . if a logic contains the rule of weakening, then premises can be freely added; this is shown schematically below, where a and b represent individual premises, and γ represents a set of premises: that is, if we can prove b from the set of premises in γ, we can also prove it from γ and some other premise a. if a logic contains the rule of contraction, extra occurences of a premise can be freely discarded: that is, if we can prove b from γ and two instances of a, we can also prove it from γ and just one instance of a. by removing these rules, a logic becomes resource sensitive in the sense that premises are resources that must be kept track of and accounted for: they can be "used up" in a way that is not the case in classical logic. this is evident in the behaviour of implication, for example. if we apply the rule of modus ponens in classical logic, we can prove not only the consequent of the conditional, but also retain both of the premises in the conclusion if we so wish: by contrast, in linear logic, modus ponens uses up both premises in proving the consequent, so that the consequent alone is left over (⊸ is linear implication, and ⊗ is multiplicative conjunction, which for present purposes can be thought of as the linear logic equivalent of ∧): all of this means that, as @xcite put it, premises in linear logic "are not contextindependent assertions that may be used or not", as in classical logic, but rather "occurrences of information which are generated and used exactly once" (emphasis in original). this seems to be a good fit with how linguistic meaning contributions behave, since they too are resource sensitive @xcite . for example, the sentence naomi loves james cannot have the meaning love(n, n) (i.e. 'naomi loves herself'), where we ignore the meaning of james and use the meaning of naomi twice. returning to glue semantics, the linear logic formulae of the meaning constructors contributed by the words of a sentence (and sometimes also by structural properties of the sentence) are premises which must all be used up in constructing a proof of the linear logic formula corresponding to the sentence as a whole. thanks to the correspondence between rules of logical deduction and operations in the lambda calculus known as the curry-howard isomorphism @xcite , each step in this proof also provides instructions for what to do with the meaning expression that forms the other part of a meaning constructor, thus providing us with the compositional semantics we are looking for. the two most important rules of linear logic which we make use of are those of implication elimination (i.e. modus ponens) and implication introduction (i.e. hypothetical reasoning). in the lambda calculus, these correspond to the operations of function application and lambda abstraction, respectively, as shown in figure 1 . in these proofs, meaning constructors are written with a colon separating the meaning expression on the left-hand side and the linear logic formula on the right-hand side. as mentioned above, the symbol ⊸ represents linear implication. figure 2 gives a more linguistic example, combining a transitive verb with its two arguments. we use the following conventions when writing proofs: unannotated λx.λy.love(x , y) : a ⊸ b ⊸ c n : a λy.love(n, y) : b ⊸ c j : b love(n, j) : c figure 2 : glue proof for naomi loves james proof steps correspond to implication elimination, and β-reduction is performed silently. for now, we continue to use arbitrary labels for the atoms in the linear logic formulae; in section 5 we will see how these can be connected (or 'glued') to the syntax. as mentioned, one of the strengths of the logical deduction approach to semantic composition is that scope ambiguities need not correspond to syntactic ambiguities. instead, they emerge from the fact that distinct proofs can (sometimes) be obtained from the same set of premises. figure 3 shows an example of this phenomenon for the scopally ambiguous sentence someone loves everyone. from the same three lexical premises (shown in labelled boxes), we can obtain two distinct proofs, via hypothetical reasoning, where the quantifiers scope in different orders: on top, we see the proof of the surface scope reading ('there is a person who loves everyone'), where everyone is applied before someone, so that the latter scopes over the former; below, we see the inverse scope reading ('everyone is loved by someone'), where the quantifiers are applied in the opposite order. both possibilities are afforded by the linear logic, without requiring different premises to begin with, which means that the same syntactic analysis can serve for both readings. ## application to dependency grammar the next question that arises is: how do we connect the linear logic formulae in meaning constructors to such a syntactic analysis, specifically in a dependency grammar setting? in the previous section, we simply used atomic formulae like a and b, but we cannot assume that the lexical entries of e.g. a verb and its subject know each other's types absolutely. instead, the formulae must be made relative, and based on the syntactic structure. there are several ways this can be done: here we adopt so-called "first-order glue" @xcite . as the name says, this is a first-order logic, where the predicates are type-constructors and the terms are nodes of the syntactic trees. by convention, we use type constructors that are mnemonic for the corresponding montagovian type on the lambda calculus side, so that e.g. e takes a tree node and constructs a linear logic type that corresponds to something of type e on the meaning side. the type of a noun, then, can be given as e( * ) ⊸ t ( * ), where * refers to the node that the noun occupies. in order to make this work, it is not enough to be able to refer to the word's own node with * ; we must also be able to refer to the syntactic context to make sure that entries "fit together". here we exploit the fact that sets of paths through the dependency tree can be expressed through regular expressions over the alphabet l ∪ {↑}, where l is the set of syntactic labels and ↑ refers to the mother node. for convenience we also use * as a start symbol. for example, assuming standard labels, * subj in a lexical entry refers to that node's subject daughter, * obj to the object daughter, * (subj|obj) to the set of the subject and object daughter, and * comp * subj to the set of subj daughters embedded under zero or more comp daughters. for the case of the transitive sentence involving quantifiers that we saw in section 4, we can use the full lexical entries in figure 4 . the terms of the linear logic (i.e. the arguments to the type construc-tors e and t ) are paths through the tree. given a syntactic tree with numbered nodes, they can be instantiated to numbers. assume that someone, loves and everyone are numbered 1, 2, 3 and that 1 and 3 are subj and obj daughters of 2 respectively. then the type of someone becomes (e(1) ⊸ t (2)) ⊸ t (2), loves gets the type e(1) ⊸ e(2) ⊸ t (2) and everyone (e(3) ⊸ t (2)) ⊸ t (2). it is easily seen that these types are isomorphic to the atomic types we used in figure 3 and so the same proofs go through. this technique can be extended to deal with elements that are semantically active but not present in the syntactic structure. first, consider the case of pro-drop. many dependency grammarians take the view that pro-dropped subjects should not be represented in the syntax, but they are obviously semantically active. to deal with this, we allow paths in lexical entries to be constructive, i.e. if a path does not lead to a node in the tree, we construct the path, making sure we pick unused numbers for the implicit nodes we need. if a second path references the same node that did not exist in the syntax, we use this number to reference it. to avoid infii 1 persuaded 2 him 3 to 4 leave 5 root subj obj xcomp mark figure 5: control infinitive nite trees, path parts under the kleene star are not interpreted constructively. when we allow constructive paths, we can deal with pro-dropped subjects by assuming that all verbs that require a subject also introduce a meaning constructor of type e( * subj) or its montague lift (e( * subj) ⊸ t ( * ↑)) ⊸ t ( * ↑). 2 the meaning side will depend on the semantics for anaphora that is adopted (if the pro-drop subject is anaphoric, as is usually the case). let us now look at the slightly more complicated example of control infinitives. these too have an implicit subject position which must be represented in the syntax, but which is often not made explicit in a dependency syntax tree. we will see how glue semantics makes it possible to nevertheless give a semantic analysis. a sample syntactic structure is given in figure 5 , with lexical entries and the linear logic proof in figures 6 7 . the fact that the object of persuade is also interpreted as the subject of the infinitive is encoded in the meaning of persuade by the fact that the variable y occurs in both positions. crucially, the constructive interpretation of paths allows us to identify e( * subj) in the meaning constructor of leave and (e( * xcomp subj) in the constructor of persuade, even if leave has no subject in the syntactic representation. finally, let us look at the more complicated example of relative clauses. we first consider english relative clauses of the type the dog that they thought we admired. figure 8 show two ways of analyzing such sentences that are found in the dependency grammar literature, differing in how that is attached. the two dashed lines show the main options: either it is attached as an object of admire, or it is attached to think as a subordinator. the first type of annotation makes explicit where the gap inside the relative clause is. the second does not; and if that is left out, there is in any case no way of indicating where the gap is in a surfaceoriented dependency analysis. in settings such as @xcite , where no lexical information is assumed, it is crucial to know where the gap is, but in the present, theoretical dependendcy grammar setting, we can assume we have access to valency information telling us that admire takes an object and think does not; therefore there is no ambiguity in where the gap is. 3 from a semantic point of view, the ordinary analysis of relative clauses in formal semantics, which we follow here, is that they denote properties or, extensionally speaking, sets. that is dog denotes the set of dogs, that they thought we admired denotes the set of things that they thought we admired, and dog that they thought we admired denotes the intersection of these sets, i.e. the entities that are dogs and that they thought we admired. the precise semantic analysis is not our agenda here, but a reasonable interpretation of that they thought we admired (simplifying away from tense and intensionality) would be λx.think (a 1 , admire(s + , x)) where a 1 is a free variable representing the anaphor they and s + is a constant referring to a group including the speaker. the lexical entries are given in figure 9 . notice that that is semantically vacuous (whether analysed as a subordinator or an object). when these meanings are instantiated with the node numbers from figure 8 , we can construct the proof in figure 10 . to save space we do not show how admire and think combine with their subjects. notice how node 9 is introduced, since the dependency tree has no object daughter of admire. this does not imply any commitment to an empty category in the syntax: the only role of this element is to provide abstraction over the gap in the relative clause. this i s : e( * ) persuaded λx.λy.λp.persuade(x, y, p (y)) : e( * subj) ⊸ e( * obj) ⊸ (e( * xcomp subj) ⊸ t ( * xcomp)) ⊸ t ( * ) him a 1 : e( * ) leave λx.admire(x) : e( * subj) ⊸ t ( * ) figure 6: lexical entries for control infinitive s : e(1) a 1 : e(3) λx.λy.λp.persuade(x, y, p (y)) : e(1) ⊸ e(3) ⊸ (e(6) ⊸ t (5)) ⊸ t (2) λp.persuade(s, a 1 , p (a 1 )) : (e(6) ⊸ t (5)) ⊸ t (2) λx.leave(x) : e(6) ⊸ t (5) persuade(s, a 1 , p (y)) : t (2) the 1 dog 2 that 3 they 4 thought 5 we 6 admired 7 barks 8 root subj det relcl subj subj comp obj subord figure 8: two styles of relative clause annotation what we call thought-relcl is different from other meaning constructors in several ways. first, it is a constructional meaning, i.e. it is not associated with a lexical item alone, but triggered by a syntactic configuration, in this case a verb that bears the relcl relation. to interpret the paths correctly, it must still be associated with a node in the tree, in this case naturally the verb of the relative clause. however, we cannot simply precombine thought-relcl and the meaning of thought because the verb must combine with its arguments first. thus, glue semantics allows us to split the meaning contributions at the interface to semantics without giving up on lexical integrity in the syntax. second, we see that this meaning constructor uses quantification over possible gaps, i.e. it requires some type e resource to be missing in the relative clause: of course, we only get a successful proof if this is instantiated to the introduced index 9 of the actually missing element, the object of admire. in this way, we can construct a proper meaning for relative clauses without a commitment to empty categories in the syntax. another virtue of this approach is that we can restrict relativization sites if needed. in figure 9 we use universal quantification, which allows all kinds of gaps, but as we mentioned above, it is also possible to use regular expressions to express non-deterministic paths. for example, if the language we analyze only allows e.g. relativization on local subjects and objects, we can use e( * (subj|obj)), and if the language allows non-local relativization, but only on subjects and objects, we can use e( * comp * (subj|obj)). whether such an interface restriction on relativization is preferrable to a purely syntactic one is an empirical question, but given the widespread avoidance of empty syntactic categories in dependency grammar, this approach at least offers an alternative. ## conclusion we have seen how glue semantics lets us connect dependency syntax analyses to formal semantics by drawing on a framework that is quite close in spirit to dependency grammar, namely lexical functional grammar. in particular, both frameworks reject the adoption of abstract syntactic analysis merely for the purpose of syntax-semantics homomorphism; and both frameworks assume lexical integrity and therefore reject decomposing lexical items in the syntax. glue semantics gives us finegrained control over the syntax-semantics interface, allowing us to achieve the effects of empty categories and lexical decomposition there while preserving the surface-oriented syntactic analyses characteristic of both frameworks. the most immediate advantage for dependency grammar is that this opens the door to the large literature in formal semantics. we have seen how we can analyse quantifier scope, control infinitives, and constructions with gaps, such as relative clauses. this is valuable in itself and can of course be extended to numerous other constructions. but there is a reason why the interface to semantics is particularly important to dependency grammar. one way of motivating the surface-oriented structures that are often adopted in dependency grammar is by delegating to semantics the work that abstract syntax does in other frameworks. but if this is to go beyond mere hand-waving, it is im-portant to accompany such claims with explicit analysis. we hope this paper has shown one way this can be done.