The objective of this paper is to study, by new formal methods, the notion
of tree code introduced by Nivat in (Tree Automata and Languages, Elsevier,
Amsterdam, 1992, pp. 1-19). In particular, we consider the notion of stabi
lity for sets of trees closed under concatenation. This allows us to give a
characterization of tree codes which is very close to the algebraic charac
terization of word codes in terms of free monoids. We further define the st
able hull of a set of trees and derive a defect theorem for trees, which ge
neralizes the analogous result for words. As a consequence, we obtain some
properties of tree codes having two elements. Moreover, we propose a new al
gorithm to test whether a finite set of trees is a tree code. The running t
ime of the algorithm is polynomial in the size of the input. We also introd
uce the notion of tree equation as complementary view to tree codes. The ma
in problem emerging in this approach is to decide the satisfiability of tre
e equations: it is a special case of second-order unification, and it remai
ns still open. (C) 2001 Elsevier Science B.V. All rights reserved.