Feature Graphs

The semantics of -constraints will be defined with respect to the domain of feature graphs. A feature graph is a finite, rooted, connected and directed graph for which the following properties must hold :

• Edges are labeled with features.
• For every node, the labels of the out-coming edges must be pairwise distinct.
• Every inner node must be a variable and
• every leaf node must be either a constant or a variable.

For example, figure 3.1 shows two possible dgs for the -constraint:

  
Figure 3.1: The left dg directly mirrors the set of atomic constraints expressed in the example -constraint, and the right dg bears additional constraints. Hence, it is more informative than the left one.

Formally, a feature graph is defined as follows (cf. [Smolka1992]) where xfs is called an f-edge (with , , and ):

• a pair (c, ), where and is the empty set; or
• a pair ( ,E), where is a variable (called the root) and E is a finite, possible empty set of edges such that
  1. if xfs and xft are in E, then s = t (i.e., features are functional)
  2. if , then E contains edges leading from the root to the node x (i.e., the graph is connected)

Thus, variables are labels of nodes, features are labels of edges, and constants are the terminal nodes of a feature graph, since no edge can leave a constant node.

A feature graph G is called a subgraph of a feature graph G' if the root of G is a variable or a constant occurring in G' and every edge of G is an edge of G'. For example,

is a subgraph of the dg of figure 3.1. The subgraphs of a feature graph G are partially ordered by

G' is a subgraph of

For example, for the subgraphs of of figure 3.1 given in figure 3.2 it holds that , , .

  
Figure 3.2: Some of the sub-dgs of the dg given in figure 3.1

According to [VanNoord1993] we define the traversal of a given feature graph and a given path as follows: For a path, and G a feature graph, and x a node of G, define x/p to be a node in G as follows: If k=0, then x/p = x. Otherwise, , if there exists an -edge (otherwise, x/p is undefined). We will use the notation G/p to mean for the root node of G.

If G is a feature graph and s is a constant or variable in G, then denotes the unique maximal subgraph of G whose root is s. For a feature graph G and a path p, denotes the subgraph , if G/p = s is defined.

For example the subgraph of the graph of figure 3.1 (i.e., the unique maximal subgraph of with root node ) is denoted by the expression .