Feature structures are related to frames in artificial intelligence
and to record structures in many programming languages. They are
widely used as a data structure for natural language processing and
their formalizations often include multiple inheritance and subtyping,
which allow for terser descriptions and a logical control over
non-determinism during search. While it is widely known that
problems
in empirical linguistics often under-determine the formal devices that
must be employed in their formal expression, it has never been
formally proven what, if anything, is gained by using subtypes,
parametric types and/or features in a feature logic. This, in
turn,
has hampered our understanding of how typed feature structures relate
to other algebraic structures used in natural language processing and
logic programming, such as systemic networks and lattices of Prolog
or
first-order terms. Given a fixed signature, a declaration of
types
and features, what kinds of information can feature structures
distinguish with types relative to what they can distinguish with
features? Are types, parametric or otherwise, just a convenient
shorthand for bundles of features? If there is a formal trade-off,
can we use that to our advantage for better ``compilation'' of
practical large-scale grammars, when viewed as logic programs over
typed feature structures?
This dissertation is a study of the algebraic structures that underlie
attributed type signatures and the universes of typed feature
structures that they induce. Specifically, it proposes definitions
of
signature subsumption and equivalence to answer these questions with
reference to the logic of typed feature structures as formalized in
[Carpenter, 1992]. In addition to the obvious advantages of
understanding what the ramifications of changing the signature of a
program/grammar are, the present study also demonstrates, with the
support of empirical results, that the view of signatures proposed
here can substantially improve the efficiency of programs written over
the logic of typed feature structures by showing how to embed a
significant class of signatures into the lattice of Prolog terms. In
so doing, it demonstrates that efficient computation with typed
feature structures reduces to the more general problems of standard
logic programming in Prolog, graph coloring and matrix multiplication.
Electronically available file formats:
@phdthesis{Penn:2000a,
author = {Gerald Penn},
title = {The Algebraic Structure of Attributed Type Signatures},
school = {School of Computer Science, Carnegie Mellon University},
year = {2000}
}