Green's equivalences in finite semigroups of binary relations (Q1318965)

Let \(D\) be a \({\mathcal D}\)-class of a semigroup \(S\) and let \(x \in D\). Let \(\{R_ i : i \in I\}\) and \(\{L_ \lambda : \lambda \in \Lambda\}\) denote the collections of \(\mathcal R\)-classes and \(\mathcal L\)-classes, respectively, of \(D\). For each \(i \in I\) and \(\lambda \in \Lambda\), let \(H_ i = R_ i \cap L_ x\) and \(H_ \lambda= L_ \lambda \cap R_ x\). Then \(\{H_ i : i \in I\}\) is the collection of all \(\mathcal H\)-classes contained in \(L_ x\) and \(\{H_ \lambda : \lambda \in \Lambda\}\) is the set of all \(\mathcal H\)-classes contained in \(R_ x\). Now let \(\{q_ \lambda : \lambda \in \Lambda\}\) and \(\{r_ i : i \in I\}\) be two subsets of \(S^ 1\) such that \(xq_ \lambda \in H_ \lambda\) and \(r_ i x \in H_ i\) for all \(\lambda \in \Lambda\) and \(i \in I\). The triple \(\{H_ x, \{q_ \lambda : \lambda \in \Lambda\},\{r_ i : i \in I\}\}\) is referred to as a complete frame of \(D\). A complete frame permits one to recover all \(\mathcal R\), \(\mathcal L\) and \(\mathcal H\) classes of \(D\). Specifically, Green's lemma implies \(R_ x = \bigcup_{\lambda \in \Lambda} H_ x q_ \lambda\), \(L_ x = \bigcup_{i \in I} r_ i H_ x\), \(R_ i = r_ i R_ x\), \(L_ \lambda = L_ xq_ \lambda\) and \(H_{i\lambda} = r_ i H_ x q_ \lambda\). In all that follows, \(S\) will be a subsemigroup of the semigroup \({\mathcal B}_ n\) of all binary relations on a set of \(n\) elements. The main results of the paper show how one can find a complete frame of any \(\mathcal D\)-class of \(S\). The regular and irregular cases are treated separately. Using these results, the author describes algorithms for producing complete frames of \(\mathcal D\)-classes and the paper closes with examples of computer computations based on these algorithms.