Alphabetic tree relations (Q1193896)

The alphabetic tree relations studied in this paper are tree transformations defined by bimorphisms (\(\varphi,R,\psi)\) in which \(\varphi\) and \(\psi\) are alphabetic tree homomorphisms and \(R\) is a recognizable tree language. The class Aleph of these tree relations is shown to contain the inverses and the compositions of its members. These transformations also preserve recognizable and algebraic tree languages. Several natural types of tree transformations are shown to be in Aleph and the class is compared with some other classes of tree transformations. A key notion in the paper is a certain join operation for combining ranked alphabets.