Computing maximal subsemigroups of a finite semigroup (Q1645462): Difference between revisions

The problem addressed in this paper is the computation of all maximal subsemigroups of a given finite semigroup. Although such a computation is obviously possible it is by no means clear that it may be carried out efficiently. Based on results of \textit{N. Graham} et al. [J. Comb. Theory 4, 203--209 (1968; Zbl 0157.04901)], which relate maximal subsemigroups of a finite semigroup with its structure in terms of Green's relations, the authors develop algorithms that completely solve the problem. A key step consists in solving the problem for regular Rees 0-matrix semigroups. The authors also carry out a number of computational experiments with their algorithms on the first few (computationally feasible) elements of previously studied families of semigroups, which are thought to somehow represent the difficulties of the calculations. The performance of the algorithms for an \(X\)-generated finite semigroup \(S\) turns out to be comparable with that of the best known procedures to compute Green's relations on \(S\) (which is \(O(|S|\,|X|)\)), which anyway is a precondition for applying the algorithms.