Back to search

University of Washington

Array TFS storage for unification grammars

Abstract

dc:description.abstract

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 <italic>typed feature structures</italic> (TFSes) describe directed graphs, allowing for the application of graph-theoretic analyses. In particular, graph <italic>unification</italic>--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 <italic>agree</italic>, 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.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Slayden, Glenn C.
Advisor dc:contributor.advisor
  • Bender, Emily M.

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • Copyright is held by the individual authors.
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1773/20770

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Slayden, Glenn C.. Array TFS storage for unification grammars. 2012. http://hdl.handle.net/1773/20770