Catalogue of Artificial Intelligence Techniques
Keywords: DAG, LFG, Lexical Functional Grammar, directed acyclic graph
Categories: Natural Language
Author(s): John Beavan
Many recent grammar theories, such as Generalised Phrase Structure Grammar, Lexical Functional Grammar, and Categorial Grammar may be expressed using the notion of Directed Acyclic Graphs (DAGs), Feature Structures, or Attribute-Value Matrices (AVMs). The grammatical information associated with an expression can be thought of as a set of partial functions (or features) defined on it, whose values may be either atomic, or a further set of partial functions. Alternatively, this may be represented by a DAG where the root node represents the expression, the directed edges are labelled by the name of a feature, and the nodes where they end represent the corresponding value. For instance, the following feature structure may represent an expression with syntactic category NP, and with an agreement feature, number, whose value is singular.
Information is then passed between linguistic entities by the operation of Graph Unification, which informally consists of `combining' two graphs to produce a third one containing the information of the first two, and nothing else, provided this information is not contradictory (in which case unification fails). For instance, the feature structure described above may unify with the similar feature structure below (which has a 3rd person agreement feature)
The result of the unification will then be the following feature structure:
- Shieber, S.M., An Introduction to Unification-Based Approaches to Grammar
, CSLI Lecture Notes No. 4.
, Stanford, 1986.