Congruence preserving functions of Wilke's tree algebras (Q2577741)

In the formalism introduced by \textit{T. Wilke} [Theor. Comput. Sci. 154, No.~1, 85--106 (1996; Zbl 0871.68110)] binary labeled trees are represented by terms over a certain 3-sorted signature \(\Sigma\) consisting of six operation symbols. A \(\Sigma\)-algebra is called a tree algebra if it satisfies four identities that determine when two \(\Sigma\)-terms of sort TREE represent the same tree. In this paper the completeness properties of Wilke's tree operations are considered. It is shown that any free tree algebra generated by a label alphabet containing at least seven elements is affine complete, that is to say, all congruence preserving operations are obtained as compositions of projections, constants and the six fundamental operations. For the operations of sorts ALPHABET and CONTEXT the result is shown to hold in somewhat stronger forms.