Pointlike sets with respect to R and J. (Q2463850)

Let \(\mathbf V\) be a pseudovariety of semigroups; a subset \(X\) of a finite semigroup \(S\) is \(\mathbf V\)-pointlike [resp. \(\mathbf V\)-idempotent pointlike] if, for each relational morphism \(\varphi\colon S\to V\) with \(V\in\mathbf V\), all elements of \(X\) relate to some common element of \(V\) [resp. idempotent of \(V\)]. The set of all \(\mathbf V\)-pointlike sets of \(S\), to be denoted by \(P_{\mathbf V}(S)\), is a subsemigroup of the semigroup \(P(S)\) of all subsets of \(S\). The paper presents algorithms to compute, for each finite semigroup \(S\) the semigroups \(P_{\mathbf R}(S)\) and \(P_{\mathbf J}(S)\) as well as the respective \(\mathbf R\)- and \(\mathbf J\)-idempotent pointlike sets. The algorithm for computing \(P_{\mathbf R}(S)\) is an analogue of Henckell's construction for the computation of the aperiodic pointlike sets \(P_{\mathbf A}(S)\). We use the following notation: for a subsemigroup \(U\) of \(P(S)\) let \(D_{\mathbf R}(U)\) be the subsemigroup of \(P(S)\) generated by all elements of the form \(\bigcup R\) where \(R\) is any \(\mathcal R\)-class of \(U\) and set \(C_{\mathbf R}(U)={\downarrow}D_{\mathbf R}(U)\) where the letter means the closure of \(D_{\mathbf R}(U)\) under subsets. The algorithm to compute \(P_{\mathbf R}(S)\) then is as follows: start with the semigroup \(S\), considered as a subsemigroup of \(P(S)\), that is, set \(S=\{\{s\}\mid s\in S\}\) and apply the operator \(C_{\mathbf R}\) repeatedly until the result becomes stable. The algorithm to compute \(P_{\mathbf J}(S)\) is different and somehow simpler (it is shown that the analogous procedure does not deliver the proper result for \(\mathbf J\)). The algorithms for the computation of the respective idempotent pointlike sets are based on the former algorithms. In the final section, some problems are stated and complexity issues are discussed.