Inclusion, Disjointness and Choice: The Logic of Linguistic Classification

INCLUSION, DISJOINTNESS AND CHOICE: THE LOGIC OF LINGUISTIC CLASSIFICATION Bob Carpenter Computational Linguistics Program Philosophy Department Carnegie Mellon University Pittsburgh, PA 15213 carp~caesar.lcl.cmu.edu Carl Pollard Linguistics Department Ohio Sate University Columbus, OH 43210 pollard~hpuxa.ircc.ohio-st ate.edu Abstract We investigate the logical structure of concepts generated by conjunction and disjunction over a monotonic multiple inheritance network where concept nodes represent linguistic categories and links indicate basic inclusion (ISA) and disjoint- hess (ISNOTA) relations. We model the distinction between primitive and defined concepts as well as between closed- and open-world reasoning. We ap- ply our logical analysis to the sort inheritance and unification system of HPSG and also to classifica- tion in systemic choice systems. Introduction Our focus in this paper is a stripped-down mono- tonic inheritance-based knowledge representation system which can be applied directly to provide a clean declarative semantics for Halliday's sys- temic choice systems (see Winograd 1983, Mel- lish 1988, Kress 1976) and the inheritance module of head-driven phrase-structure grammar (HPSG) (Pollard and Sag 1987, Pollard in press). Our in- heritance networks are constructed from only the most rudimentary primitives: basic concepts and ISA and ISNOTA links. By applying general al- gebraic techniques, we show how to generate a meet semilattice whose nodes correspond to con- sistent conjunctions of basic concepts and where meet corresponds to conjunction. We also show how to embed this result in a distributive lattice where the elements correspond to arbitrary con- junctions and disjunctions of basic concepts and where meet and join correspond to conjunction and disjunction, respectively. While we do not consider either role- or attribute-based reasoning in this paper, our constructions are directly appli- cable as a front-end for the combined attribute- and concept-based formalisms of Ait-Kaci (1986), Nebel and Smolka (1989), Carpenter (1990), Car- penter, Pollard and Franz (1991) and Pollard (in press). The fact that terms in distributive lattices have disjunctive normal forms allows us to factor our construction into two stages: we begin with the consistent conjunctive concepts generated from our primitive concepts and then form arbitrary disjunctions of these conjunctions. The conjunc- tive construction is useful on its own as its result is a semilattice where meet corresponds to conjunc- tion. In particular, the conjunctive semilattice is ideally suited to conjunctive logics such as those employed for unification, as in HPSG. We will consider the distinction between prim- itive and defined concepts, a well-known distinc- tion expressible in terminological reasoning sys- tems such as KL-ONE (Brachman 1979, Brach- man and Schmolze 1985), and its descendants (such as LOOM (MacGregor" 1988) or CLASSIC (Borgida et al. 1989)). We also tackle the va- riety of closed-world reasoning that is necessary for modeling constraint-based grammars such as HPSG. A similar form of closed-world reasoning is supported by LOOM with the disjoint-covering construction. One of the benefits of our notion of inheritance is that it allows us to express the natural seman- tics of both systemic choice systems and HPSG in- heritance hierarchies using basic concepts and ISA and ISNOTA links. In particular, …

Content truncated to 500 words