Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Graph Unification

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:



Add Comment

No comments.