COMPLEXITY PSEUDOVARIETIES ARE NOT LOCAL: TYPE II SUBSEMIGROUPS CAN FALL ARBITRARILY IN COMPLEXITY
From MaRDI portal
Publication:5493859
DOI10.1142/S0218196706003177zbMath1105.20049OpenAlexW2037840685MaRDI QIDQ5493859
Benjamin Steinberg, John L. Rhodes
Publication date: 16 October 2006
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218196706003177
Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items (5)
Degree 2 transformation semigroups as continuous maps on graphs: Complexity and examples ⋮ John Rhodes and the theory of finite semigroups. ⋮ An effective lower bound for group complexity of finite semigroups and automata ⋮ Krohn-Rhodes complexity pseudovarieties are not finitely based ⋮ Infinite-vertex free profinite semigroupoids and symbolic dynamics.
Cites Work
- Infinite iteration of matrix semigroups. II: Structure theorem for arbitrary semigroups up to aperiodic morphism
- Categories as algebra: An essential ingredient in the theory of monoids
- Infinite iteration of matrix semigroups. I: Structure theorem for torsion semigroups
- Decidability of complexity one-half for finite semigroups
- Kernel systems - a global study of homomorphisms on finite semigroups
- On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties.
- Subsemigroups and complexity via the presentation lemma
- On aperiodic relational morphisms.
- Complexity of finite semigroups
- Improved lower bounds for the complexity of finite semigroups
- INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES
- ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART I
- Group-complexity and reversals of finite semigroups
- On The Profinite Topology on a Free Group
- IDEMPOTENT POINTLIKE SETS
- Krohn-Rhodes complexity pseudovarieties are not finitely based
- On Pointlike Sets and Joins of Pseudovarieties
- The fundamental lemma of complexity for arbitrary finite semigroups
This page was built for publication: COMPLEXITY PSEUDOVARIETIES ARE NOT LOCAL: TYPE II SUBSEMIGROUPS CAN FALL ARBITRARILY IN COMPLEXITY
