Handling Linear Precedence Constraints by Unification

HANDLING LINEAR PRECEDENCE CONSTRAINTS BY UNIFICATION Judith Engelkamp, Gregor Erbach and Hans Uszkoreit Universitfit des Saarlandes, Computational Linguistics, and Deutsches Forschungszentrum fiir Kiinstliche lntelligenz D-6600 Saarbriicken 11, Germany engelkamp@coli.uni-sb.de ABSTRACT Linear precedence (LP) rules are widely used for stating word order principles. They have been adopted as constraints by HPSG but no encoding in the formalism has been provided. Since they only order siblings, they are not quite adequate, at least not for German. We propose a notion of LP constraints that applies to linguistically motivated branching domains such as head domains. We show a type-based encoding in an HPSG-style formalism that supports processing. The encoding can be achieved by a compilation step. INTRODUCTION Most contemporary grammar models employed in computational linguistics separate statements about dominance from those that determine linear precedence. The approaches for encoding linear precedence (LP) statements differ along several dimensions. Depending on the underlying grammatical theory, different criteria are employed in formulating ordering statements. Ordering constraints may be expressed by referring to the category, grammatical function, discourse r61e, and many other syntactic, semantic, morphological or phonological features. Depending on the grammar formalism, different languages are used for stating the constraints on permissible linearizations. LP rules, first proposed by Gazdar and Pullum (1982) for GPSG, are used, in different guises, by several contemporary grammar formalisms. In Functional Unification Grammar (Kay 1985) and implemented versions of Lexical Functional Grammar, pattern languages with the power of regular expressions have been utilized. Depending on the grammar model, LP statements apply within different ordering domains. In most frameworks, such as GPSG and HPSG, the ordering domains are local trees. Initial trees constitute the ordering domain in ID/LP TAGS (Joshi 1987). In current LFG (Kaplan & Zaenen 1988), functional precedence rules apply to functional domains. Reape Research for this paper was mainly carried out in the project LILOG supported by IBM Germany. Some of the research was performed in the project DISCO which is funded by the German Federal Ministry for Research and Technology under Grant-No.: ITW 9002. We wish to thank our colleagues in SaarbriJcken, three anonymous referees and especially Mark Hepple for their valuable comments and suggestions. (1989) constructs word order domains by means of a special union operation on embedded tree domains. It remains an open question which choices along these dimensions will turn out to be most adequate for the description of word order in natural language. In this paper we do not attempt to resolve the linguistic issue of the most adequate universal treatment of word order. However we will present a method for integrating word order constraints in a typed feature unification formalism without adding new formal devices. Although some proposals for the interaction between feature unification and LP constraints have been published (e.g. Seiffert 1991), no encoding has yet been shown that integrates LP constraints in the linguistic type system of a typed feature unification formalism. Linguistic processing with a head-driven phrase structure grammar (HPSG) containing LP constraints has not yet been described in the …

Content truncated to 500 words