tailieunhanh - Báo cáo khoa học: "EXTENDED GRAPH UNIFICATION"

W e 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, without incurring significant extra computational overheads in the process of unification. W e illustrate the notation with examples from a categorial description of a fragment of English, and discuss the computational properties of unification of DAGs specified in this way. . | EXTENDED GRAPH UNIFICATION Allan Ramsay School of Cognitive Sciences University of Sussex Palmer BN1 9QN Abstract We propose an apparently minor extension to Kay s 1985 notation for describing dữected acyclic graphs DAGs . The proposed notation permits concise descriptions of phenomena which would otherwise be difficult to describe without incurring significant extra computational overheads in the process of unification. We illustrate the notation with examples from a categorial description of a fragment of English and discuss the computational properties of unification of DAGs specified in this way. 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 complex feature structures Gazdar 1988 . Grammars are specified in terms of partial descriptions of syntactic structures programs that depend on these grammars perform some variant of unification in order to investigate the relationship between specific strings of words and the syntactic structures permitted by the grammar is some sentence grammatical what actually is its syntactic 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 extension to the languages used by Kay and Shieber for describing graphs and to the specification of the conditions under which graphs untfy. This extension enables US to write concise descriptions of syntactic phenomena which would be awkward to specify using the original notations. We do not argue that our extension makes it possible to describe any phenomena which could not have beer described at all using the existing .