Catalogue of Artificial Intelligence Techniques
Keywords: ALE, C, CUF, DAG, LFG, LIFE, Lexical Functional Grammar, Pascal, TDL, TFS, directed acyclic graph, typed feature structures
Categories: Natural Language
Author(s): Nicolas Nicolov
Feature Structures are structured objects which consist of a set of attributes (features) and their corresponding values. FSs are much like frames in AI systems, records of imperative programming languages like C or Pascal, and the feature descriptions in standard theories of phonology, and more recently in syntax. The value of an attribute in a FS can in turn be a structured object (FS). FSs can be seen as labelled tuples. Two features (possibly at different levels of nesting) can share their value (can be token identical). This is called reentrancy or coreference. Because FSs allow reentrancy in general they are not labelled trees but Directed Acyclic Graphs (DAGs). The main operation on FSs is feature structure unification which takes two FSs and attempts to find the most general FS that is compatible with them. Unification of FSs is a simple form of merging. FSs can be seen as partial descriptions of (linguistic) objects--unification can always add new features (with their values) or further specify an embedded FS (see Graph Unification). Typed feature structures are like ordinary feature structures except that each feature structure (node in the DAG) has an associated type (or sort) that identifies what type of object the structure is modelling. The set of all types is partially ordered and each type has an associated list of valid features that can be specified for it. FSs have found wide use in theoretical linguistics: sorts in constraint-based grammars (such as HPSG), Lexical Functional Grammar (LFG), feature bundles, feature matrices or categories (in GPSG), functional structures (in FUG), DAGs (in PATR-II). Recent computational linguistics frameworks are based on feature structures (ALE, TFS, CUF, TDL, etc.). Even programming languages use FSs as their basic data structures ( -terms in LIFE are a generalisation of typed feature structures).
- Gazdar G. and Mellish, C.S., Natural Language Processing in PROLOG
, Addison Wesley, Wokingham, England, 1989 (Sect 7.2; pp.230-235; Sect 7.10