Next: Solutions of constraints Up: The constraint language: Previous: Constraints

## Feature graphs

The semantics of employing labels L, constants C, and variables V is defined with respect to the domain of feature graphs, built from L, C, and V. A feature graph is a directed graph which is finite, rooted, and connected. Furthermore, the labels of the edges leaving a node must be pairwise distinct. Every inner node of a feature graph is a variable, and every terminal node is either a variable or a constant. Edges are triples Xlt such that X is a variable, l is a label and t is either a variable or a constant.

Definition 5 (Feature graphs)   A feature graph is
• a pair (c,) where c is a constant and is the empty set; or
• a pair (X0, E) where X0 is a variable (the root) and E is a set of edges such that
• if Xls and Xlt are both in E then s = t; i.e. labels are functional; and
• if Xls is in E then X is reachable from X0 by the edges in E; i.e. feature graphs are connected.

Note that this definition implies that no edges leave constant nodes, because edges always start with a variable. A node s is reachable from a node t in a feature graph F iff t s where is the transitive and reflexive closure of which is a binary relation on the nodes occurring in F:

t s iff tls

The following notation to traverse feature graphs is introduced. If F is a feature graph and p is a path, then F/p is the variable or constant that is reached from the root of F where the labels in the path correspond to the labels of the edges. For example consider the following feature graph

which is graphically represented in figure 2.1.

The expression F1/l2l4 denotes c2; and F1/l2 = X1. Furthermore, F1/l3 is undefined.

More formally, for p = l1...lk a path, and t a node (variable or atom), define t/p to be the node given as follows. If k = 0 then t/p = deft. Otherwise, t/l1...lk is defined to be the node t' if there is an edge labelled l1 from t to t'' and t' = t''/l2...lk (otherwise t/l1...lk is undefined). Furthermore, for F a feature graph with root X0, F/p = defX0/p.

A feature graph F is called a subgraph of a feature graph F' if the root of F is a variable or atom occurring in F' and every edge of F is an edge of F'. If F is a feature graph and s a node of F, then Fs denotes the unique maximal subgraph of F of which the root is s. In that case, Fs has as its root the node s, and as its edges are all those edges of the form tlt' present in F such that both t, t' are reachable from s in F. For example, if F1 is the feature graph in figure 2.1, then we have:

Furthermore, for F a feature graph and p a path, Fp denotes the subgraph Fs where F/p = s, if this is defined. For example:

Otherwise Fp is undefined.

Next: Solutions of constraints Up: The constraint language: Previous: Constraints
Noord G.J.M. van
1998-09-30