Trees, band monoids and formal languages (Q1910641)

The authors endow the free monoid \(\{e,s\}^*\) with the structure of a binary tree as follows: the left [right] son of a word \(\alpha\in\{e,s\}^*\) is the word \(s\alpha\) [resp. \(e\alpha\)]. A binary tree is called inertial if each left [right] son \(x\) has a left [right] son \(y\) and the binary trees of descendants of \(x\) and \(y\) are isomorphic. The lattice of all inertial subtrees of the binary tree \(\{e,s\}^*\) (including the empty subtree) is shown to be isomorphic to the lattice of all varieties of band monoids (Theorem 3.2). Let \(\Gamma(V)\) be the inertial subtree of \(\{e,s\}^*\) corresponding to a variety \(V\) of band monoids, \(A\) a set. A mapping \(\varphi\) assigning a subset of \(A\) to each vertex of \(\Gamma(V)\) is called admissible if \(\varphi(y)\) is obtained by removing an element from \(\varphi(x)\) whenever \(y\) is a son of \(x\) and \(\varphi(x)\) is non-empty. Then the set of all admissible mappings with a suitable multiplication yields a model for the \(A\)-generated relatively free monoid of the variety \(V\) (Theorem 3.8). Finally, the authors describe the atoms of the boolean algebra of \(V\)-recognizable languages over \(A\) (Theorem 4.5).