Array TFS storage for unification grammars

Constraint-based grammar formalisms such as Head-Driven Phrase Structure Grammar
(HPSG) model linguistic entities as sets of attribute-value tuples headed by types drawn from a
connected multiple-inheritance hierarchy. These typed feature structures (TFSes) describe directed
graphs, allowing for the application of graph-theoretic analyses. In particular, graph unification—
the computation of the most general structure that is consistent with a set of argument
graphs (if such a structure exists)—can be interpreted as expressing the satisfiability and
combination functions for the represented linguistic entities, thus providing a principled method
for describing syntactic elaboration. In competent natural language grammars, however, the
graphs are typically large and numerous, and computational efficiency is a key engineering
concern. This thesis describes a method for the storage of typed feature structures where each
TFS comprises a self-contained, contiguous memory allocation with a tabular internal structure.
Also detailed is an efficient unification algorithm for this storage mode. The techniques
are evaluated in agree, a new managed-execution concurrent unification chart parser which
supports both syntactic analysis (parsing) and surface realization (generation) within the
framework of the DELPH-IN (Deep Linguistic Processing with HPSG Initiative) joint reference
formalism.