PERIODICITIES ON TREES

We introduce the notion of periodicity for k-ary labeled trees: roughl y speaking, a tree is periodic if it can be obtained by a sequence of concatenations of a smaller tree plus a ''remainder''. The period is t he shape of such smaller tree (i.e. the corresponding unlabeled tree). This definition reduces to the classical one for string when restrict ed to the case of unary trees. Then, we define the greatest common div isor of two unlabeled trees and relate right congruences to unlabeled trees. This allows us to give a characterization of tree periodicity i n terms of right congruences and then to prove a periodicity theorem f or trees that is a generalization to trees of the Fine and Wilf's peri odicity theorem for words. (C) 1998-Elsevier Science B.V. All rights r eserved.