LILOG Report LR-33, May 1988. To appear in: J. Wedekind and C. Rohrer (eds.), Unification in Grammar; The MIT Press, 1991. This paper presents a set description logic with subsorts, feature selection (the inverse of unary function application), agreement, intersection, union and complement. We define a model theoretic open world semantics and show that sorted feature structures constitute a canonical model, that is, without loss of generality subsumption and consistency of set descriptions can be considered with respect to feature structures only. We show that deciding consistency of set descriptions is an NP-complete problem.
Download PDF Show BibTeX
Login to edit