An Attributive Logic of Set Descriptions and Set Operations

An Attributive Logic of Set Descriptions Set Operations Suresh Manandhar HCRC Language Technology Group The University of Edinburgh 2 Buccleuch Place Edinburgh EH8 9LW, UK Internet: Suresh. Manandhar@ed. ac. uk and Abstract This paper provides a model theoretic semantics to fea- ture terms augmented with set descriptions. We pro- vide constraints to specify HPSG style set descriptions, fixed cardinality set descriptions, set-membership con- straints, restricted universal role quantifications, set union, intersection, subset and disjointness. A sound, complete and terminating consistency checking proce- dure is provided to determine the consistency of any given term in the logic. It is shown that determining consistency of terms is a NP-complete problem. Subject Areas: feature logic, constraint-based gram- mars, HPSG 1 Introduction Grammatical formalisms such as HPSG [Pollard and Sag, 1987] [Pollard and Sag, 1992] and LFG [Kaplan and Bresnan, 1982] employ feature de- scriptions [Kasper and Rounds, 1986] [Smolka, 1992] as the primary means for stating linguistic theories. However the descriptive machinery employed by these formalisms easily exceed the descriptive machinery available in feature logic [Smolka, 1992]. Furthermore the descriptive machinery employed by both HPSG and LFG is difficult (if not impossible) to state in fea- ture based formalisms such as ALE [Carpenter, 1993], TFS [Zajac, 1992] and CUF [D6rre and Dorna, 1993] which augment feature logic with a type system. One such expressive device employed both within LFG [Kaplan and Bresnan, 1982] and HPSG but is unavailable in feature logic is that of set descriptions. Although various researchers have studied set de- scriptions (with different semantics) [Rounds, 1988] [Pollard and Moshier, 1990] two issues remain unad- dressed. Firstly there has not been any work on consi- stency checking techniques for feature terms augmen- ted with set descriptions. Secondly, for applications within grammatical theories such as the HPSG forma- lism, set descriptions alone are not enough since de- scriptions involving set union are also needed. Thus to adequately address the knowledge representation needs of current linguistic theories one needs to provide set descriptions as well as mechanisms to manipulate these. In the HPSG grammar forma- lism [Pollard and Sag, 1987], set descriptions are em- ployed for the modelling of so called semantic indices ([Pollard and Sag, 1987] pp. 104). The attribute INDS in the example in (1) is a multi-valued attribute whose value models a set consisting of (at most) 2 objects. However multi-valued attributes cannot be descri- bed within feature logic [Kasper and Rounds, 1986] [Smolka, 1992]. (1) Io DREL --4 °~TIs~R[] / Ls'~E~ w J [NDS IRESTINAME ~andy ]['IRESTINAME kim II ¢ L L N*M" D JIL L JJJ A further complication arises since to be able to deal with anaphoric dependencies we think that set mem- berships will be needed to resolve pronoun dependen- cies. Equally, set unions may be called for to incremen- tally construct discourse referents. Thus set-valued extension to feature logic is insufficient on its own. Similarly, set valued subcategorisation frames (see (2)) has been considered as a possibility within the HPSG formalism. (2) believes= IYNILOCISUBCAT~ [[SYN~LOOIHEADICAT …

Content truncated to 500 words