Tameness of pseudovariety joins involving R. (Q814806): Difference between revisions

The concept of ``tameness'' (with respect to an implicit signature \(\sigma\)) has been much studied recently in the context of decidability of semidirect products of pseudovarieties of semigroups and monoids. Roughly speaking, \(\sigma\)-tameness of a pseudovariety \(\mathbf V\) consists of two ingredients: (i) the decidability of the word problem for the free \(\sigma\)-\(\mathbf V\)-semigroup and (ii) \(\sigma\)-reducibility of \(\mathbf V\). The latter means that each system of equations of a certain kind (defined by a graph theoretic condition) admits a solution (under certain constraints) in any member of \(\mathbf V\) only if it admits a corresponding solution in the free \(\sigma\)-\(\mathbf V\)-semigroup. In the main part of the paper, the authors prove that for the ``standard'' implicit signature \(\sigma=\kappa=\{\cdot,{}^{\omega-1}\}\), all pseudovariety joins of the form \(\mathbf R\vee\mathbf W\) with \({\mathbf W}\subseteq [\![xy^{\omega+1}z=xyz]\!]\), \(\mathbf W\) \(\kappa\)-tame, are \(\kappa\)-tame (and a fortiori are decidable). This, in particular, holds for the joins \(\mathbf R\vee\mathbf{Com}\), \(\mathbf R\vee\mathbf G\) and \(\mathbf R\vee\mathbf{CR}\). The proof is based on quite delicate arguments involving profinite combinatorics of the free pro-\(\mathbf R\)-trivial monoid. At the beginning of the paper some additional results concerning the complete \(\sigma\)-reducibility (and therefore complete \(\sigma\)-tameness) of joins with subpseudovarieties of \(\mathbf J\) are established, where ``complete'' refers to a generalization of that notion defined by allowing more general systems of equations. The reviewer was informed that in work under preparation a complete reducibility result for \(\mathbf R\) is obtained by the same authors.