Flexible Structural Analysis of Near-Meet-Semilattices for Typed Unification-Based Grammar Design

Proceedings of COLING 2012: Technical Papers, pages 833–848, COLING 2012, Mumbai, December 2012. Flexible Structural Analysis of Near-Meet-Semilattices for Typed Unification-based Grammar Design Rouzbeh FARAHMAN D Gerald PENN University of Toronto {rouzbeh,gpenn}@cs.toronto.edu Abstract We present a new method for directly working with typed unification grammars in which type unification is not well-defined. This is often the case, as large-scale HPSG grammars now usually have type systems for which many pairs do not have least upper bounds. Our method yields a unification algorithm that compiles quickly and yet is nearly as fast during parsing as one that requires least upper bounds. The method also provides a natural naming convention for unification results in cases where no user-defined type exists. Keywords: HPSG, typed feature structures, unification-based grammar. 833 1 Introduction In Head-driven Phrase Structure Grammars (HPSG, Pollard and Sag, 1994), most of the on-line computation time is spent performing unifications. HPSG type systems are typically large and involve subtyping, so computing a unification involves computing a join, the least informative type that is subsumed by both of the argument feature structures’ types.1 Early TFS-based parsing systems like ALE (Carpenter and Penn, 1996) required that every pair of unifiable types have a least common supertype, i.e., joins are uniquely defined wherever they need to be defined. Type hierarchies that have this requirement are called meet semi-lattices (MSLs) (Davey and Priestley, 2002), because the existence of a meet for every pair of types is sufficient to guarantee the existence of a join for every unifiable pair of types when the type hierarchy is finite. Later HPSG parsing systems such as the LKB (Copestake and Flickinger, 2000) and PET (Callmeier, 2000) eliminated this restriction, and it is now extremely rare to find a decent-sized HPSG with an MSL type hierarchy. The LKB, at least in some early versions, used an on-line caching algorithm to add joins to the user-defined type system when necessary. PET adds all of the necessary joins in advance, during a grammar compilation stage. In either case, the time it costs to perform these repairs is proportional to the number of new joins that must be added. It therefore makes some sense to strive to add the least number of types necessary. While modern HPSG type systems are never MSLs in practice, they are always almost MSLs, in a sense that can be made mathematically precise, which we do here for the first time. Converting an HPSG type system to an MSL would be horrendously slow if it were not the case that HPSGs were almost MSLs already, because an exponential number of types need to be added in the worst case. There is another cost hidden in this method, furthermore, at least when we strive to add the least number of extra types necessary. In this case, naming these types is also a challenge. Figure 1(a), for example, shows an input type hierarchy that is not an MSL. In Figure 1(b), it has been converted into an MSL by adding one …

Content truncated to 500 words