Syntactic Theory
Feature Structures | ''Real'' Feature Structures >
Feature Graphs
Feature graphs are defined over a signature consisting of non-empty, finite disjoint sets of features and of atoms. The features are used to encode properties of (linguistic) objects, such as NUMBER, GENDER etc. The atoms are used for the values of such features, as in plural, feminine etc. We depict features in CAPITALS and atoms in italics. We usually assume that these sets are non-empty.
The arcs of a feature graph are labelled by features. The root is a designated node from which all other nodes are accessible. Nodes with no outgoing edges are called leaves. They can be marked by an atom, or be unmarked. A feature graph is empty if it consists of a single unmarked node with no arcs and atomic if it consists of a single marked node with no arcs.
We use the following conventions:
- A, B to refer to feature graphs
- Q, q, δ, θ refer to constituents of feature graphs. δ is a transition relation and θ is an atom labelling/ typing function
- the root is depicted as a grey-coloured node, usually at the top or the left side of the graph
- the identities of the nodes are arbitrary. We use generic names such as q0, q1 etc to refer to them.
Paths
A path is a finite sequence of features leading from the root to some node. Every sequence of features constitutes a path. A path is a purely syntactic notion.
Reentrancy
A feature graph is reentrant if there are two distinct paths in it.
Cycles
A cycle is a special case of reentrancy: every cyclic feature graph is reentrant, but not vice versa. The linguistic motivation for cycles is very limited; however, there are good practical reasons for allowing them: when implementing a system it is easier to support cycles than to guarantee that all the graphs are acyclic. Unification can yield a cyclic graph even when its operands are acyclic.
Subsumption
One feature graph can subsume another if it is more general, or put differently, a feature graph can be subsumed by another one if it is more specific.
