5.4.5 Treeness Constraints

Our formal framework simply stipulated that models should be trees. In the constraint model, we provide an explicit axiomatization of this notion. A tree is a directed acyclic graph, where every node has a unique incoming edge, except for a distinguished node, called the root, which has none.

To support our axiomatization, we introduce two new variables $\Feature{mother}(w)$ and $\Feature{daughters}(w)$ for each node . Again to avoid the problem that $\Feature{mother}$ might be undefined at the root, we make it denote a set:

$\begin{array}{r} \Feature{mother}(w)\subseteq\VV\\ \Feature{daughters}(w)\subseteq\VV \end{array}$

$\Feature{mother}(w)$ denotes the set of mothers of and $\Feature{daughters}(w)$ the set of its immediate daughters. To enforce that a node has at most one mother, we pose:

$|\Feature{mother}(w)|\leq 1$

The set of immediate daughters of is simply defined as the union of its daughter sets:

$\Feature{daughters}(w)=\bigcup\limits_{\rho\in\text{\setof{Roles}}}\rho(w)$

is a mother of iff is a daughter of :

$w\in\Feature{mother}(w')\quad\equiv\quad w'\in\Feature{daughters}(w)$

We could introduce a variable to denote the root, but instead we introduce the variable $\SET{rootset}$ to denote the singleton containing the root.

$\begin{array}{c} \SET{rootset}\subseteq\VV\\ |\SET{rootset}|=1 \end{array}$

Now, is root iff it has no mother:

$w\in\SET{rootset}\quad\equiv\quad |\Feature{mother}(w)|=0$

So far, we have enforced that every node (except the root) has a unique mother, but it could still have more than one incoming edge from the same mother. We can exclude this case by stating that the daughter sets for all nodes together with the root set form a partition of the input words:

$\VV=\SET{rootset}\uplus \biguplus\limits_{\text{\shortstack{$w\in\VV$\\$\rho\in\setof{Roles}$}}}\rho(w)$

In order to guarantee well-formedness, we still need to enforce acyclicity.