4.1 Descriptions of Trees

Since trees are a basic food group in the computational linguist's diet, it is often very convenient to be able to describe classes of trees with certain general structural properties. As mentioned earlier, a tree is typically specified extensionally by listing its edges, i.e. by providing a relation of immediate dominance between vertices. This is often too specific, hence the idea of also permitting the more relaxed relation of (general) dominance, which is simply the transitive closure of immediate dominance.

This makes it possible to express that some vertex v_1 should dominate another vertex v_2, which we write v_1\LE
v_2, without having to commit to any specific detail. This merely requires that v_2 must occur below v_1, and allows arbitrary material to be inserted on the path between them. In other words, math/v_1\LE v_2/ is satisfied in every model (tree) in which v_1 denotes a proper ancestor of v_2.



Denys Duchier
Version 1.2.0 (20010221)