10.2 Finite and Infinite Trees

A finite tree is an atom or a tuple of finite trees. For instance f(f(a b) g(a f(c))) is a finite tree. A finite tree is uniquely determined by its tree domain and a labeling function. The tree domain of a tree is the set of path leading from its root to its nodes. The labeling function maps a path to the label at the node reachable by this path. In the above example, the tree domain D is the set D={epsilon,1,11,12,2,21,22,221}; the labeling function L is given by: L(epsilon)=f, L(1)=f, L(11)=a, L(12)=b, L(2)=g, L(21)=a, L(22)=f, and L(221)=c.

ept that its tree domain is infinite. In other words, an infinite tree can is defined by an infinite tree domain and a labeling function. For instance, f(f(f(...))) is an infinite tree whose tree domain D is the set {epsilon,1,11,111,...}. Infinite trees can be considered as a unwinding of rooted graphs. Infinite trees matter for programming since they allow to model cyclic data structures for constraint programming.


Denys Duchier, Claire Gardent and Joachim Niehren
Version 1.3.99 (20050412)