6533b871fe1ef96bd12d2308

RESEARCH PRODUCT

Equations on trees

Antonio RestivoSabrina Mantaci

subject

Discrete mathematicsTree (data structure)Combinatorics on wordsBinary treeTree codeMathematics

description

We introduce the notion of equation on trees, generalizing the corresponding notion for words, and we develop the first steps of a theory of tree equations. The main result of the paper states that, if a pair of trees is the solution of a tree equation with two indeterminates, then the two trees are both powers of the same tree. As an application, we show that a tree can be expressed in a unique way as a power of a primitive tree. This extends a basic result of combinatorics on words to trees. Some open problems are finally proposed.

yearjournalcountryeditionlanguage
1996-01-01
https://doi.org/10.1007/3-540-61550-4_169