Tractability and Structural Closures in Attribute Logic Type Signatures

Tractability and Structural Closures in Attribute Logic Type Signatures Gerald Penn Department of Computer Science University of Toronto 10 King’s College Rd. Toronto M5S 3G4, Canada gpenn@cs.toronto.edu Abstract This paper considers three assumptions conventionally made about signatures in typed feature logic that are in po- tential disagreement with current prac- tice among grammar developers and linguists working within feature-based frameworks such as HPSG: meet-semi- latticehood, unique feature introduc- tion, and the absence of subtype cover- ing. It also discusses the conditions un- der which each of these can be tractably restored in realistic grammar signatures where they do not already exist. 1 Introduction The logic of typed feature structures (LTFS, Car- penter 1992) and, in particular, its implementa- tion in the Attribute Logic Engine (ALE, Car- penter and Penn 1996), have been widely used as a means of formalising and developing gram- mars of natural languages that support computa- tionally efficient parsing and SLD resolution, no- tably grammars within the framework of Head- driven Phrase Structure Grammar (HPSG, Pollard and Sag 1994). These grammars are formulated using a vocabulary provided by a finite partially ordered set of types and a set of features that must be specified for each grammar, and feature struc- tures in these grammars must respect certain con- straints that are also specified. These include ap- propriateness conditions, which specify, for each type, all and only the features that take values in feature structures of that type, and with which types of values (value restrictions). There are also more general implicational constraints of the form �� � , where � is a type, and � is an expres- sion from LTFS’s description language. In LTFS and ALE, these four components, a partial order of types, a set of features, appropriatenessdeclara- tions and type-antecedent constraints can be taken as the signature of a grammar, relative to which descriptions can be interpreted. LTFS and ALE also make several assump- tions about the structure and interpretation of this partial order of types and about appropriateness, some for the sake of generality, others for the sake of efficiency or simplicity. Appropriate- ness is generally accepted as a good thing, from the standpoints of both efficiency and representa- tional accuracy, and while many have advocated the need for implicational constraints that are even more general, type-antecedent constraints at the very least are also accepted as being necessary and convenient. Not all of the other assumptions are universally observed by formal linguists or gram- mar developers, however. This paper addresses the three most contentious assumptions that LTFS and ALE make, and how to deal with their absence in a tractable manner. They are: 1. Meet-semi-latticehood: every partial order of types must be a meet semi-lattice. This implies that every consistent pair of types has a least upper bound. 2. Unique feature introduction: for every fea- ture, F, there is a unique most general type to which F is appropriate. 3. No subtype covering: there can be feature structures of a non-maximally-specific type that …

Content truncated to 500 words