On the solidity of general varieties of tree languages. (Q2861065)

It is well known that ``the pre-image of a regular tree language under any tree homomorphism is also regular, but few known families of special regular tree languages share this property.'' Varieties are well studied families of regular tree languages which are closed under Boolean operations (intersection, union and complement), and pre-images of contexts and (pre-images of) pure tree homomorphisms. Generalized varieties of tree languages (and algebras and congruences) have been introduced and studied by the author starting from [Theor. Comput. Sci. 205, No. 1-2, 1-43 (1998; Zbl 0913.68115)]. In generalized varieties neither the leaf alphabets (\(X\)'s) nor the ranked alphabets (\(\Sigma\)'s) are fixed. ``This is a good framework here, too, as tree homomorphisms typically change the ranked alphabets of trees, and as many natural families of regular tree languages are known to be GVTLs. We may also note that the definition of GVTLs already involves a mild solidity condition.''NEWLINENEWLINE A substitution is a tree homomorphism which maps any \(m\)-ary function symbol from a ranked alphabet to an \(m\)-ary leaf-less context (parameter-free polynomial in \(m\) variables) possibly in another ranked alphabet. A family of substitutions is called a category if it is closed under the composition of substitutions, contains all the alphabetic substitutions (the ones which map every \(m\)-ary function symbol to some \(m\)-ary function symbol) and contains the substitutions whose composition with an alphabetic substitution is already a member of the category. For such a category \(\mathcal K\) of substitutions, a generalized variety of tree languages is called \(\mathcal K\)-solid if it is closed under the pre-images of any substitution in \(\mathcal K\).NEWLINENEWLINE The main result of the paper is a three-fold variety theorem for generalized \(\mathcal K\)-solid varieties of tree languages, generalized \(\mathcal K\)-solid varieties of finite algebras, and generalized \(\mathcal K\)-solid varieties of finite congruences (the congruences with finitely many equivalence classes). For various categories of substitutions, solidity of many instances of generalized varieties of tree languages (such as nilpotent, definite, reverse definite, generalized definite, locally testable, piecewise testable, and aperiodic), and the corresponding algebras and congruences, are studied in the paper. It is noted in the paper that some results and instances parallel those of \textit{P. Baltazar} [Acta Cybern. 18, No. 4, 719-731 (2008; Zbl 1164.68022)] but the author has preferred ``an independent presentation that develops the needed conceptual framework for the theory of general varieties.''NEWLINENEWLINE The paper is a very well-written, well-organized, and well-motivated piece of work which could be used for continuing this line of research. One typo (among very few in the paper) is the clause (1) on page 26 which should have been NEWLINE\[NEWLINE\mathrm{sub}(x)=\{x\},\quad\mathrm{hg}(x)=0\quad\text{and}\quad\mathrm{root}(x)=x\quad\text{for any }x\in X;\tag{1}NEWLINE\]NEWLINE note that, by the convention of the paper, there is no \(0\)-ary symbol in a ranked alphabet \(\Sigma\).