Logic and Feature Structures

Abstract

Feature structures play an important role in linguistic knowledge representation in computational linguistics. Given the proliferation of different feature structure formalisms it is useful to have a common language to express them in. This paper shows how a variety of feature structures and constraints on them can be expressed in predicate logic (except for the use of circumscription for non-monotonic devices), including sorted feature values, subsumption constraints and the non-monotonic ANY values and constraint equations. Many feature systems can be completely axiomatized in the Schonfinkel-Bernays class of first-order formulae, so the decidability of the satisfiability and validity problems for these systems follows immediately.