Recursive Coloration of Trees
by
Slavcho Shtrakov
South-West University

Hypersubstitutions are mappings which assign n-ary term with each n-ary operation symbol. Let \tau is a given type and k in \nn be an natural number, called initial number (or initial color). Let

\Sigma = (\sigma1, \sigma2, ... )

be a sequence of hypersubstitutions, \nn_\F be the set {1, 2, ... , maxar} where maxar is the maximum of the arity of operation symbols and \eta:\nn_\F×\nn --> \nn be a function, called coloring. The pair \zeta_k=(\Sigma, \eta) is called hypercoloration with initial color k. The image [^(\zeta)]_k[t] of a term (tree) t is defined as follows:
[^(\zeta)]_k[t]:=t for t in X \cup \F₀ and
[^(\zeta)]_k[f(t₁, ... , t_n)]: = \sigma_k(f)([^(\zeta)]_{\eta(1, k)}[t₁], ... , [^(\zeta)]_{\eta(n, k)}[t_n]).

So, the colors of the children t₁, ... , t_n are recursively determined by the color of the parent t. The hypercolorations allows us to generalize the concept of hypersubstitutions working over colored trees (terms) i.e. trees whose nodes are supplied with colors. Usually the colors are integers. This concept is important in different fields of Computer Science - Graphical User Interface (GUI), XML - technology, Object Oriented Programming etc.

The monoid Hyp(\tau) of all hypersubstitutions of type \tau is a submonoid of the monoid Hypc_k(\tau) of all hypercolorations of type \tau which is not countable.

In this paper we obtain some internal results concerning hypercolored derived algebras, hypercolored varieties and hypercolored identities, generated by hypercolorations.

Date received: April 27, 2004