An Algorithm for Generation in Unification Categorial Grammar

AN ALGORITHM FOR GENERATION IN UNIFICATION CATEGORIAL GRAMMAR Jonathan Calder, Mike Reape and Henk Zeevat University of Edinburgh Centre for Cognitive Science 2 Buccleuch Place Edinburgh EH8 9LW Abstract We present an algorithm for the generation of sentences from the semantic representations of Unification Categorial Grammar. We discuss a variant of Shieber's semantic monotonicity requirement and its utility in our algorithm. We indicate how the algorithm may be extended to other grammars obeying the same requirement. Appendices contain a full listing of the program and a trace of execution of the algorithm. 1. Introduction In this paper we present an algorithm for generating sentences using unification categorial grammars (UCGs, Zeevat et al. 1987) but which extends to any categorial grammar with unification (e.g., categorial unification grammars, Uszkoreit 1986, Karttunen 1987). We relate the algorithm to proposals by Shieber (1988). Following Shieber, we address the basic generation problem; that is, given a syntactic category K and a semantic representation ~, generate every possible string def'med by the grammar of category K with a semantic representation that is logically equivalent to ~. In more concrete terms, this means that we dispense with any planning component and directly address the intrinsic complexity of the basic generation problem. The development of such algorithms is as fundamentally important as the corresponding work on parsing algorithms. We also discuss the properties of a semantic representation language (SRL) and the manner of its construction which makes our algorithm effective. The crucial property is a stricter form of Shieber's (1988) property of semantic monotonicity. We not only require that the semantics introduced by all subconstituents of an expression appear within the semantics of the expression as a whole; we also require that the semantics of any containing expression be a further instantiation of one of its subexpressions. We introduce the algorithm on a case-by-case basis, at each stage extending its coverage and include a listing of the program implementing this algorithm, as appendix A. 2. Basis of the algorithm The most important feature of categorial grammars is the close correspondence of syntactic and semantic ftmctors. In generation, if the semantic functor of an expression can be identified, possible values of the syntactic functor can also be determined. Under these circumstances, a simple recursive procedure can be stated which implements a mixed top-down and bottom-up strategy, alternately determining the functor of an expression and generating the arguments to that functor. In the presentation of the basic algorithm below we will make the simplifying assumption that for any formula of the semantic representation language, the syntactic and semantic functors are immediately identifiable. We will have to relax this restriction in order to deal with phenomena such as type raising and identity semantics. UCG employs only two types of phrase structure rules. First, there are two binary rules of forward and backward application. Schematically, these can be represented as follows. Result -~ Functor/Active Active Result --~ Active Functor\Active The first of the actual rules is stated below. The second is just …

Content truncated to 500 words