Green's equivalences in finite semigroups of binary relations
type: Item
instance of: scholarly article
title: Green's equivalences in finite semigroups of binary relations
zbMATH Open document ID: 0805.20059
DOI: 10.1007/BF02573672
author: Janusz Konieczny
published in: Semigroup Forum
publication date: 1995-02-08T00:00:00Z
full work available at URL: https://eudml.org/doc/135314
review text: 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.
Mathematics Subject Classification ID: 20M20
Mathematics Subject Classification ID: 20M15
zbMATH DE Number: 549066
zbMATH Keywords: semigroups of binary relations
zbMATH Keywords: Green's relations
zbMATH Keywords: algorithms
zbMATH Keywords: complete frames of \(\mathcal D\)-classes
reviewed by: jun. Kenneth D. Magill
describes a project that uses: AUTOMATE
MaRDI profile type: Publication
cites work: AUTOMATE, a computing package for automata and finite semigroups
cites work: Q3897157
cites work: Q5628367
cites work: Q5545552
cites work: Q4126563
cites work: On generating regular elements in the semigroup of binary relations
cites work: Q3853827
cites work: On the determination of Green's relations in finite transformation semigroups
cites work: Une représentation fidele des groupes d'un monoide de rélations binaires sur un ensemble fini
cites work: Q4173578
cites work: On the semigroup of binary relations
description: scientific article; zbMATH DE number 549066