Paper: Extended Graph Unification

ACL ID E89-1029
Title Extended Graph Unification
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1989

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 lang...