Extended Graph Unification

EXTENDED GRAPH UNIFICATION Allan Ramsay School of Cognitive Sciences University of Sussex, Falmer BN1 9QN Abstract We propose an apparently minor extension to Kay's (1985} notation for describing directed acyclic graphs (DAGs}. The proposed notation permits concise descriptions of phenomena which would otherwise be difficult to describe, with- out incurring significant extra computational over- heads in the process of unification. We illustrate the notation with examples from a categorial de- scription of a fragment of English, and discuss the computational properties of unification of DAGs specified in this way. argue that our extension makes it possible to de- scribe any phenomena which could not have been described at all using the existing notations, just that the descriptions using the extension are more concise. 2 GRAPH SPECIFICATION We start by defining a language GSL (graph spec- ification language} for describing graphs, and by specifying the conditions under which two graphs unify. 1 INTRODUCTION Much recent work on specifying grammars for fragments of natural languages, and on producing computational systems which make use of these grammars, has used partial descriptions of com- plex feature structures {Gazdar 1988}. Gram- mars are specified in terms of partial descriptions of syntactic structures; programs that depend on these grammars perform some variant of unifica- tion in order to investigate the relationship be- tween specific strings of words and the syntac- tic structures permitted by the grammarmis some sentence grammatical, what actually is its syn- tactic structure, how can some partially specified structure be realised as a string of words, and so on. Nearly all existing unification grammars of this kind use either term unification (the kind of unification used in resolution theorem provers, and hence provided as a primitive in PROLOG) or some version of the graph unification proposed by Kay {1985) and Shieber (1984). We propose an ex- tension to the languages used by Kay and Shieber for describing graphs, and to the specification of the conditions under which graphs unify. This ex- tension enables us to write concise descriptions of syntactic phenomena which would be awkward to specify using the originM notations. We do not 2.1 GSL: syntax The syntax of GSL has been kept as close as possi- ble to that of FUG (Kay 1985) in order to facilitate comparisons. It is not, unfortunately, possible to keep it close to both FUG and PATR (Shieber 1984), but it should be possible for readers famil- iar with PATR to see roughly what the relation between the two is. A node descriptor consists of either an atomic symbol, e.g. agr, cat, bar, or of two atomic symbols separated by a slash, e.g. cat/C, head/OBJECT. In the first case the symbol is the value of the described node, in the second the sym- bol before the slash is the node's value and the symbol after it is its name. We will generally use lower case words for values and upper case ones for names, but the distinction between upper and lower case has no significance in …

Content truncated to 500 words