A LOGICAL SEMANTICS FOR FEATURE STRUCTURES 
 
 Unification-based grammar formalisms use structures containing sets of features to describe linguistic objects . Although computational algorithms for unification of feature structures have been worked out in experimental research, these algorithms become quite complicated, and a more precise description of feature structures is desirable. We have developed a model in which descriptions of feature structures can be regarded as logical formulas , and interpreted by sets of directed graphs which satisfy them. These graphs are, in fact, transition graphs for a special type of deterministic finite automaton . This semantics for feature structures extends the ideas of Pereira and Shieber [11], by providing an interpretation for values which are specified by disjunctions and path values embedded within disjunctions . Our interpretation differs from that of Pereira and Shieber by using a logical model in place of a denotational semantics . This logical model yields a calculus of equivalences , which can be used to simplify formulas . Unification is attractive, because of its generality, but it is often computationally inefficient. Our model allows a careful examination of the computational complexity of unification . We have shown that the consistency problem for formulas with disjunctive values is NP-complete . To deal with this complexity , we describe how disjunctive values can be specified in a way which delays expansion to disjunctive normal form . 