Sequences of Hypersubstitutions and Coloring
by
Slavcho Shtrakov
South-West University

Hypersubstitutions are mappings which assign n-ary term with each n-ary operation symbol. If [^(\sigma)] is the extension of a hypersubstitution \sigma onto the set of all terms and t \approx s is an identity in the variety V i.e. t \approx s in Id Vthen it is called hyperidentity if [^(\sigma)][t] \approx [^(\sigma)][s] in Id V for all \sigma. A variety V is called solid if all identities of V are hyperidentities.

Let \Sigma = (\sigma₁, \sigma₂, ... ) be a sequence of hypersubstitutions and \eta:N×N --> N be a function(called coloring). The k-th result [^(\Sigma)]_k[t] of the term t by \Sigma and \eta is defined by the following recursive equations [^(\Sigma)]_k[x]:=x for x in X and [^(\Sigma)]_k[f(t₁, ... , t_n)]: = \sigma_k(f)([^(\Sigma)]_{\eta(1, k)}, ... , [^(\Sigma)]_{\eta(n, k)}).

The sequences of hypersubstitutions allows us to generalize the concept of hypersubstitutions working over colored trees (terms) i.e. trees whose nodes are supplied with colors. This concept is important in different fields of Computer Science - GUI (graphical user interface), XML -programming and XML - technology, OOP (object oriented programming) etc.

The set SHyp(\tau) of all sequences of hypersubstitutions of type \tau homomorphically includes the set Hyp(\tau) of all hypersubstitutions of type \tau and SHyp(\tau) is not countable. An identity t \approx s is called s-hyperidentity in V if for every sequence \Sigma of hypersubstitutions there is a positive integer m with [^(\Sigma)]_m[t] \approx [^(\Sigma)]_m[s] in IdV. The variety V is s-solid if every identity from Id V is s-hyperidentity.

In this paper we want to introduce the sequences of hypersubstitutions and to obtain more internal results concerning the set SHyp(\tau), s-solid varieties and s-hyperidentities, generated by sequences of hypersubstitutions.

http://www.fmns.swu.bg/~shtrakov/

Date received: February 6, 2002

Copyright © 2002 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caht-19.