RISC Forum

We consider systems of equations whose right hand-sides are finite tree transformations. We show that such systems have least solutions.  In fact they have two types of (least) solutions, the so-called [IO] and OI according to the tree substitution operation we use to solve them. A tree transformation is u-equational (u=3D[IO], OI) if it is obtained as the union of some components of the least u-solution of a system of equations of tree transformations. We characterize u-equational tree transformations in terms of bimorphisms, and we state equational characterizations for some well-known classes of tree transformations. Furthermore, we investigate the relationship between the classes of [IO]-equational and OI-equational tree transformations. Finally, we show that a Mezei-Wright type result holds for u-equational tree ransformations.