On the extension problem for partial permutations
Karl Auinger, Benjamin Steinberg · Proceedings of the American Mathematical Society · 2003
A family of pseudovarieties of solvable groups is constructed, each of which has decidable membership and undecidable extension problem for partial permutations. Included are a pseudovariety $\mathbf {U}$ satisfying no non-trivial group identity and a metabelian pseudovariety $\mathbf {Q}$. For each of these pseudovarieties $\mathbf {V}$, the inverse monoid pseudovariety $\mathbf {Sl}\ast \mathbf {V}$ has undecidable membership problem. As a consequence, it is proved that the pseudovariety operators $\ast$, $\ast \ast$, $\textcircled {m}$, $\diamondsuit$, $\diamondsuit _n$, and $\mathbf {P}$ do not preserve decidability. In addition, several joins, including $\mathbf {A}\vee \mathbf {U}$, are shown to be undecidable.