Tree codes and the defect theorems for trees

Sabrina Mantaci
LIAFA

My research background at the time I joined ALAPEDES (January 1999) was mainly in the field of combinatorics on words and language theory. More in details the research I developed in order to relate my Ph.D thesis and in the following period, was devoted to the generalization to k-ary node-labeled trees of notions, properties and results of the combinatorial theory of words. In particular problems like extending the notion of ``code'', ``equation'', ``periodicity'', together with the connected theories, have been successfully studied. Under this point of view, many of the theorems of combinatorics of words can be seen like a special case of theorems in combinatorics on trees, but, in the same time, some properties do not have a corresponding property for trees, due to their branching and asymmetric top-down/bottom-up structure. As a concrete example, here we consider the notion of tree code and the defect theorem, and their extention to the tree case. The defect theorem is one of the fundamental results of the combinatorial theory of words. It states that if a set X of words of cardinality n satisfies a nontrivial relation, then its elements can be expressed as a catenation of the words in another set Y having cardinality at most n-1. Actually there does not exist just one, but several results which formalize the above defect effect depending on the properties we require on Y(i.e., for instance, to be a code, a prefix/suffix code). We look at which defect theorems on words can be extended to trees. It turns out that in many cases this is possible. However, interestingly, the proofs are not just translations, but contain several different features compared to those for words. Moreover, due to the above differences, some results cannot be extended.

I just began to investigate some specific problems in the field of Discrete Event Systems. (max,+)-automata on words have been studied a lot, they are an important modelling tool for Discrete Event Systems. It seems interesting to study their counterpart for trees, that is (max,+)-tree automata.