gen!hegner
This paper appeared in the Proceedings of the Fifth Conference of the European Chapter of
the Association for Computational Linguistics, Berlin, 911 April 1991, pp. 3338.
Abstract
The notion of a Horn extended feature structure (Hoxf) is introduced, which is a feature
structure constrained so that its only allowable extensions are those satisfying some set of
Horn clauses in feature-term logic. Hoxfs greatly generalize ordinary feature structures in
admitting explicit representation of negative and implicational constraints. In contradistinc-
tion to the general case in which arbitrary logical constraints are allowed (for which the best
known algorithms are exponential), there is a highly tractable algorithm for the unication
of Hoxfs. The research reported herein was performed while the author was visiting the COSMOS Computational
Linguistics Group of the Mathematics Department at the University of Oslo. He wishes to thank Jens Erik
Fenstad and the members of that group for providing a stimulating research environment. Particular thanks
are due Tore Langholm for many invaluable discussions regarding the interplay of logic, feature structures,
and unication. 1.
PRELIMINARY CONCEPTS
1.1
Unication-based grammar formalisms Unication-based grammar formalisms
constitute a cornerstone of many of the most important approaches to natural-language
understanding (Shieber, 1986), (Colban, 1988), (Fenstad et al., 1989). The basic idea is
that the parser generates a number of partial representations of the total parse, which are
subsequently checked for consistency and combined by a second process known as a unier.
A common form of representation for the partial representations is that of feature structures,
which are record-like data structures which are allowed to grow in three distinct ways: by
adding missing values, by adding attributes, and by coalescing existing attributes (forcing
them to be the same). The last operation may lead to cyclic structures, which we do
not exclude. If the feature structure S
2
is an extension of S
1
(i.e., S
1
grows into S
2
by
application of some sequence of the above rules), we write S
1
S
2
and say that S
1
subsumes
S
2
. Intuitively, if S
1
S
2
, S
2
contains more information than does S
1
. It is easy to show
that
is a partial order on the class of all feature structures.
Each feature structure represents partial information generated during the parse. To
obtain the total picture, these partial components must be combined into one consistent piece
of knowledge. The formal process of unication is precisely this operation of combination.
The most general unier (mgu) S
1
S
2
of feature structures S
1
and S
2
is the least feature
structure (under
) which is larger than both S
1
and S
2
. Such an mgu exists if and only if
S
1
and S
2
are consistent; that is, if and only if they subsume a common feature structure.
1.2
Unication algorithms and this paper While the idea of a most general unier
is a pleasing theoretical notion, its real utility rest with the fact that there are ecient algo-
rithms for its computation. The fastest known algorithm, identied by A�t-Kaci (1984), runs
in time which is, for all practical purposes, linear in the size of the input (i.e., the combined
sizes of the structures to be unied). In proposing any extension to the basic framework,
a primary consideration must be the complexity of the ensuing unication algorithm. The
principal contribution of the research summarized here is to provide an extension of ordi-
nary feature structures, admitting negation and limited disjunction, while at the same time
continuing to admit a provably ecient unication algorithm.
Due to space limitations, we must omit substantial background material from this paper.
Specically, we assume that the reader is familiar with the notation and denitions sur-
rounding feature structures (Shieber, 1986; Fenstad et al., 1989), as well as the traditional
unication algorithm (Colban, 1990). We also have been forced to omit much detail from
the description and verication of our algorithm. A full report on this work will be available
in the near future.
2.
UNIFICATION IN THE PRESENCE OF
CONSTRAINTS
2.1
Constraints on feature structures Not every feature structure is a possibility as
the ultimate output of the parsing mechanism. Typically, there are constraints which must
1 be observed. One way of ensuring this sort of consistency is to build the checks right into
the grammar, so that the feature structures generated are always legitimate substructures
of the nal output. The CLG formalism (Damas and Varile, 1989) is an example of such a
philosophy. In many ways, this is an attractive option, because it provides a unied context
for expressing all aspects of the grammar. However, this approach has the disadvantage
that it limits the use of independent parsing subalgorithms whose results are subsequently
unied, since the consistency checks must be performed before the feature structures are
presented to the unier. Therefore, to maintain such independence, it would be a distinct
advantage if some of the constraint checking could be relegated to the unication process.
To establish a formal framework in which this is possible, we must start by extending
our notion of a feature structure. Following the ideas of Moshier and Rounds (1987) and
Langholm (1989), we dene an extended feature structure to be a pair N, K in which K is
a set of feature structures and N is the least element of K under the ordering
. (Thus,
by denition, K has a least element, and K determines N.) Think of N as the current
feature structure, and K as the set of all structures into which N is allowed to grow. We
dene N
1
, K
1
x
N
2
, K
2
to mean precisely that K
2
K
1
. In other words, the set of all
structures which N
2
can grow into is a subset of those which N
1
can grow into. (It follows
necessarily that N
1
N
2
in this case.) Note that if we identify the ordinary feature structure
N with the pair N, {M | N
M} , we precisely recapture ordinary subsumption. Finally,
the notion of unication associated with
x
is given by
M
1
, K
1
x
M
2
, K
2
=
M, K
1
K
2
if K
1
K
2
has a least element M;
undened
otherwise.
2.2
Logical feature structures with constraints To operate on pairs of the form
N, K algorithmically, we must have in place an appropriate representation for the set K.
There are many possible choices; ours is to let it be the set of all structures satisfying a
set of sentences in a particular logic. The logic which we use is a simple modication of
the language of Rounds and Kasper (1986) (see also (Kasper and Rounds, 1990)) admitting
negation but only binary path equivalences. Specically, an atomic feature term is one of
the following.
Formula Semantics
The identically true term. The identically false term.
( : a)
The path (nesting of attributes) exists and terminates with label a.
(
)
The paths and have a common end point (coalesced end points).
In ( : a), the label a may be , denoting a missing value. The notation (
) is borrowed
from (Langholm, 1989), and has the same semantics as {, } of (Rounds and Kasper, 1986).
A (general) feature term is built up from atomic feature terms using the connectives , ,
and �, with the usual semantics. In particular, the negation we use is the classical notion;
2 a structure satises (�) if and only if it does not satisfy . For any set of feature terms,
Mod() denotes the set of all feature structures for which each is true. For a formal
denition of satisfaction, we refer the reader to the above-cited references. Intuitively, any
set of terms which denes a consistent rooted, directed graph is satisable. However, let us
specically remark that only nodes with no outgoing edges may have labels other than
,
that labels other than
may occur at at most one end point, that no two outgoing edges
from the same node may have the same label, and that any term of the form ( : ) is
equivalent to , and so inconsistent.
Now we dene a logical extended feature structure (LoXF) to be an extended feature struc-
ture N, K in which K = Mod() for some consistent nite set of feature terms. In partic-
ular, Mod() must have a least model. We also denote this pair by F = N , Mod() .
Now F
1
x
F
2
reduces to Mod(
2
) Mod(
1
), and
F
1
x
F
2
= F
1

2
if Mod(
1

2
)
has a least element under
;
undened
otherwise.
2.3
Remark on negation A full discussion of the nature of negation in LoXFs is
complex, and will be the focus of a separate paper. However, because this topic has received
a great deal of attention (Moshier and Rounds, 1987), (Langholm, 1989), (Dawar and Vijay-
Shanker, 1990), we feel it essential to remark here that F does not have the classical
negation semantics which can be determined by looking solely at the least element. Indeed,
the appropriate denition is that F satises � precisely when no member of Mod()
satises ; in other words, the structure N is not allowed to be extended to satisfy .
2.4
Unication algorithms for logical extended feature structures In view of the
denition immediately above, it is easy to see that that any unication algorithm for LoXFs
must solve the following two problems in the course of attempting to unify F
1
and F
2
.
(u1) It must decide whether or not
1

2
is consistent; i.e., whether or not there is a
feature structure satisfying all sentences of both
1
and
2
.
(u2) In case that
1

2
is satisable, it must also determine if there is a least model, and
if so, identify it.
Now it is well known that (u1) is an NP-complete problem, even if we disallow negation
and path equivalence (Rounds and Kasper, 1986, Thm. 4). Therefore, barring the eventuali