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

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Normalize DOI.
 
(3 intermediate revisions by 3 users not shown)
Property / DOI
 
Property / DOI: 10.1016/j.jalgebra.2018.01.044 / rank
Normal rank
 
Property / OpenAlex ID
 
Property / OpenAlex ID: W2438852179 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1606.05583 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algorithm 457: finding all cliques of an undirected graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computing maximal subgroups of finite groups. / rank
 
Normal rank
Property / cites work
 
Property / cites work: The worst-case time complexity for generating all maximal cliques and computational experiments / rank
 
Normal rank
Property / cites work
 
Property / cites work: ON THE MAXIMAL SUBSEMIGROUPS OF SOME TRANSFORMATION SEMIGROUPS / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5416296 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The maximal subsemigroups of semigroups of transformations preserving or reversing the orientation on a finite chain / rank
 
Normal rank
Property / cites work
 
Property / cites work: The maximal subsemigroups of the ideals of some semigroups of partial injections / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5416278 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximal subsemigroups of the semigroup of all mappings on an infinite set / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximal subsemigroups of finite transformation and diagram monoids / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2759625 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algorithms for computing finite semigroups / rank
 
Normal rank
Property / cites work
 
Property / cites work: Path-based depth-first search for strong and biconnected components / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximal subsemigroups of finite semigroups / rank
 
Normal rank
Property / cites work
 
Property / cites work: On finite 0-simple semigroups and graph theory / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5394098 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the maximal subsemigroups of the semigroup of all monotone transformations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximality properties of some subsemigroups of Baer-Levi semigroups / rank
 
Normal rank
Property / cites work
 
Property / cites work: Completely O-simple semigroups and their associated graphs and groups / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4846425 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Two variants of the Froidure-Pin algorithm for finite semigroups / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximal subsemigroups containing a particular semigroup / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ideal Structure of the Kauffman and Related Monoids / rank
 
Normal rank
Property / cites work
 
Property / cites work: On maximal subsemigroups of Baer-Levi semigroups / rank
 
Normal rank
Property / cites work
 
Property / cites work: On cliques in graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5302760 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Depth-First Search and Linear Graph Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5709168 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximal subsemigroups of finite transformation semigroups \(K(n,r)\). / rank
 
Normal rank
Property / cites work
 
Property / cites work: A classification of maximal subsemigroups of finite order-preserving transformation semigroups / rank
 
Normal rank
Property / cites work
 
Property / cites work: MAXIMAL SUBSEMIGROUPS OF THE FINITE SINGULAR TRANSFORMATION SEMIGROUP / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1016/J.JALGEBRA.2018.01.044 / rank
 
Normal rank

Latest revision as of 00:39, 11 December 2024

scientific article
Language Label Description Also known as
English
Computing maximal subsemigroups of a finite semigroup
scientific article

    Statements

    Computing maximal subsemigroups of a finite semigroup (English)
    0 references
    0 references
    0 references
    0 references
    22 June 2018
    0 references
    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.
    0 references
    0 references
    computational semigroup theory
    0 references
    computational group theory
    0 references
    maximal subsemigroups
    0 references
    algorithms
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers