In this chapter we take up the identity conditions that are imposed on feature structures and their substructures and conclude that this is the most significant difference between feature structures and first-order terms. We then consider how more term-like identity conditions may be imposed on feature structures by enforcing extensionality conditions which identify feature structures on the basis of their feature values. Cycles pose interesting issues for determining identity conditions and we study two forms of extensionality which differ in how they treat cyclic feature structures. In the weaker system, feature structures are identified if their feature values are shared. In the stronger system, which mimics the identity conditions of Prolog II, a variant of Aczel's (1988) bisimulations are used to define identity conditions.

Identity in Feature Structures

In standard treatments of feature structures, such as those of Pereira and Shieber (1984) and Rounds and Kasper (1986), it is assumed that there are two types of feature structures: atoms, which do not take values for any features, and feature structures, which can take values for arbitrary collections of features. The standard models of these structures employ directed graphs with atoms labeling some subset of the terminal nodes (nodes without any feature arcs going out of them). It is also usually assumed that there can only be one copy of any atom in a feature structure, so that if we know that a path π1 leads to an atom a and a path π2 leads to the same atom a, then the two paths must be structure shared. In Rounds and Kasper's treatment, this is enforced by requiring the type assignment function to be one to one.