2 - Feature structures

Summary

Motivated by the violations of the context-free grammar G₀, discussed in the previous chapter, we now extend the CFG formalism with additional mechanisms that will facilitate the expression of information that is missing in G₀ in a uniform and compact way. The core idea is to incorporate into the grammar the properties of symbols in terms of which violations of G₀ were stated. Properties are represented by means of feature structures. As we show in this chapter, feature structures provide a natural representation for the kind of linguistic information that grammars specify, a natural (partial) order on the amount of information stored in these representations and an efficient operation for combining the information stored in two representations.

We begin this chapter with an overview of feature structures, motivating their use as a representation of linguistic information (Section 2.1). We then present four different views of these entities. We begin with feature graphs (Section 2.2), which are just a special case of ordinary (labeled, directed) graphs. The well-studied mathematical and computational properties of graphs make this view easy to understand and very suitable for computational implementation. This view, however, introduces a level of arbitrariness, which is expressed in the identities of the nodes. We therefore introduce two additional views. One, simply called feature structures (Section 2.3), is defined as equivalence classes of isomorphic feature graphs, abstracting over node identities. The other, called abstract feature structures (Section 2.4), uses sets rather than graphs and is easy to work with mathematically.