Improved lower bounds for the complexity of finite semigroups
If \(S\) and \(T\) are semigroups then \(S| T\) means that \(S\) is a homomorphic image of a subsemigroup of \(T\). A semigroup is called combinatorial if it contains trivial subgroups only. \((X,T)\) is a semigroup \(T\) of transformations of a set \(X\). All semigroups considered are finite. For every semigroup \(S\) there exists a sequence of transformation semigroups such that \(S| (X_n,T_n)\wr \cdots \wr(X_1,T_1)\) where \(\wr\) denotes the wreath product of transformation semigroups. Factors in the above wreath product are alternately transformation groups and combinatorial semigroups. The minimal possible number of groups in the above wreath product is called the group complexity of \(S\) and is denoted by \(\#_C(S)\). The authors define two distinctly different types of semigroups: if \(T\) is a subsemigroup of type II of a semigroup \(S\) of type I, then \(\#_C(T)<\#_C(S)\). Clearly, this device helps in evaluating the group complexity of semigroups. The semigroups of both types are studied in the paper (which, in a sense, may be considered as a continuation to the previous paper by the authors [J. Pure Appl. Algebra 1, 79--95 (1971; Zbl 0259.20051)]. There are given new lower bounds of group complexity; it is shown that there exist semigroups of arbitrary complexity whose idempotents generate a combinatorial semigroup.
- An effective lower bound for group complexity of finite semigroups and automata
- Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
- On identical transformations in commutative semigroups
- Green's relations in finite transformation semigroups
- Subsemigroups and complexity via the presentation lemma
- On aperiodic relational morphisms.
- Green's relations in deterministic finite automata
- On nonpermutational transformation semigroups with an application to syntactic complexity
- Complexity of the word problem for commutative semigroups of fixed dimension
- On the Decidability of Iterated Semidirect Products with Applications to Complexity
- Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
- Complexity of finite semigroups
- Decomposition and complexity of finite semigroups
- Embedding Theorems for Semigroups
- scientific article; zbMATH DE number 3179521 (Why is no real title available?)
- scientific article; zbMATH DE number 3287733 (Why is no real title available?)
- scientific article; zbMATH DE number 3353593 (Why is no real title available?)
- Lower bounds for complexity of finite semigroups
- On finite 0-simple semigroups and graph theory
- Proof of the fundamental lemma of complexity (strong version) for arbitrary finite semigroups
- Proof of the fundamental lemma of complexity (weak version) for arbitrary finite semigroups
- Some results on finite semigroups
- The fundamental lemma of complexity for arbitrary finite semigroups
- On a conjecture of Rhodes
- Decidability of complexity one-half for finite semigroups
- New results on the conjecture of Rhodes and on the topological conjecture
- Type-II conjecture is true for finite \(\mathcal J\)-trivial monoids
- Kernel systems - a global study of homomorphisms on finite semigroups
- Completely regular semigroup varieties generated by Mal'cev products with groups
- Lower bounds for the \(\pi\)-length of (finite) \(\pi\)-solvable semigroups
- On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties.
- Covers for regular semigroups and an application to complexity
- The \(\mathbf G\)-exponent of a pseudovariety of semigroups
- DLP in semigroups: algorithms and lower bounds
- Membership of \(\mathbf A\vee\mathbf G\) for classes of finite weakly abundant semigroups.
- Finite abundant semigroups in which the idempotents form a subsemigroup.
- John Rhodes and the theory of finite semigroups.
- Decomposition and complexity of finite semigroups
- Representations of semigroups by linear transformations. I
- Constructing divisions into power groups
- On the Dowling and Rhodes lattices and wreath products
- Semigroups whose idempotents form a subsemigroup
- ON ITERATED MAL'CEV PRODUCTS WITH A PSEUDOVARIETY OF GROUPS
- BRET TILSON: HIS LIFE AND WORK
- MODULES
- A profinite approach to stable pairs.
- A topological approach to a conjecture of Rhodes
- scientific article; zbMATH DE number 59506 (Why is no real title available?)
- A NEW PROOF OF THE RHODES TYPE II CONJECTURE
- ON SEMIGROUPS WHOSE IDEMPOTENT-GENERATED SUBSEMIGROUP IS APERIODIC
- The minimal number of generators of a finite semigroup.
- Krohn-Rhodes complexity pseudovarieties are not finitely based
- ON THE HYPERDECIDABILITY OF PSEUDOVARIETIES OF GROUPS
- PROFINITE METHODS IN SEMIGROUP THEORY
- An effective lower bound for group complexity of finite semigroups and automata
- Relative Abelian kernels of some classes of transformation monoids
- COMPLEXITY PSEUDOVARIETIES ARE NOT LOCAL: TYPE II SUBSEMIGROUPS CAN FALL ARBITRARILY IN COMPLEXITY
- Abelian kernels, profinite topologies and the extension problem
- Degree 2 transformation semigroups as continuous maps on graphs: Complexity and examples
- Complexity of finite semigroups: history and decidability
- Reduction theorem for the type-II conjecture for finite monoids
- Pointlike sets and separation: a personal perspective
- Complexity of the identity checking problem for finite semigroups.
This page was built for publication: Improved lower bounds for the complexity of finite semigroups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2559565)
