Krohn-Rhodes complexity pseudovarieties are not finitely based

DOI10.1051/ita:2005016zbMath1083.20050OpenAlexW2068906344MaRDI QIDQ4680740

Benjamin Steinberg, John L. Rhodes

Publication date: 7 June 2005

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2005__39_1_279_0

zbMATH Keywords

wreath productspseudovarieties of finite monoidspseudoidentity basesKrohn-Rhodes complexity

Mathematics Subject Classification ID

General structure theory for semigroups (20M10) Varieties and pseudovarieties of semigroups (20M07) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (4)

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 ⋮ COMPLEXITY PSEUDOVARIETIES ARE NOT LOCAL: TYPE II SUBSEMIGROUPS CAN FALL ARBITRARILY IN COMPLEXITY

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infinite iteration of matrix semigroups. II: Structure theorem for arbitrary semigroups up to aperiodic morphism
• Infinite iteration of matrix semigroups. I: Structure theorem for torsion semigroups
• A reduction theorem for complexity of 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
• Decomposition and complexity of finite semigroups
• 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
• STABLE PAIRS
• 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
• HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
• IDEMPOTENT POINTLIKE SETS
• 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
• On finite 0-simple semigroups and graph theory
• The fundamental lemma of complexity for arbitrary finite semigroups

This page was built for publication: Krohn-Rhodes complexity pseudovarieties are not finitely based