An effective lower bound for group complexity of finite semigroups and automata

DOI10.1090/S0002-9947-2011-05379-1zbMath1260.20075arXiv0812.3499OpenAlexW1979795169MaRDI QIDQ5389413

Karsten Henckell, Benjamin Steinberg, John L. Rhodes

Publication date: 26 April 2012

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0812.3499

zbMATH Keywords

iterated wreath productsKrohn-Rhodes complexitycomplexity of finite semigroupsflow latticesgroup mapping monoids

Mathematics Subject Classification ID

Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (5)

Pointlike sets for varieties determined by groups ⋮ Degree 2 transformation semigroups as continuous maps on graphs: Complexity and examples ⋮ John Rhodes and the theory of finite semigroups. ⋮ Pro-aperiodic monoids via saturated models ⋮ Degree 2 transformation semigroups as continuous maps on graphs: Foundations and structure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Categories as algebra: An essential ingredient in the theory of monoids
• k-transformation semigroups and a conjecture of Tilson
• An upper bound for the complexity of transformation semigroups
• Decidability of complexity one-half for finite semigroups
• On the complexity of finite semigroups
• A reduction theorem for complexity of finite semigroups
• Proof of the fundamental lemma of complexity (strong version) for arbitrary finite semigroups
• Kernel systems - a global study of homomorphisms on finite semigroups
• Pointlike sets: the finest aperiodic cover of a finite semigroup
• Subsemigroups and complexity via the presentation lemma
• On aperiodic relational morphisms.
• Complexity of finite semigroups
• Decomposition and complexity of finite semigroups
• Proof of the fundamental lemma of complexity (weak version) for arbitrary finite semigroups
• A class of geometric lattices based on finite groups
• Improved lower bounds for the complexity of finite semigroups
• Lower bounds for complexity of finite semigroups
• INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES
• A PROFINITE APPROACH TO STABLE PAIRS
• APERIODIC POINTLIKES AND BEYOND
• ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART I
• On The Profinite Topology on a Free Group
• On the Decidability of Iterated Semidirect Products with Applications to Complexity
• A NEW PROOF OF THE RHODES TYPE II CONJECTURE
• Krohn-Rhodes complexity pseudovarieties are not finitely based
• COMPLEXITY PSEUDOVARIETIES ARE NOT LOCAL: TYPE II SUBSEMIGROUPS CAN FALL ARBITRARILY IN COMPLEXITY
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• The fundamental lemma of complexity for arbitrary finite semigroups

This page was built for publication: An effective lower bound for group complexity of finite semigroups and automata