Krohn-Rhodes complexity pseudovarieties are not finitely based

DOI10.1051/ITA:2005016MaRDI QIDQ4680740zbMATH OpenOpenAlexFDO

Authors 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, http://www.numdam.org/item?id=ITA_2005__39_1_279_0/, https://eudml.org/doc/92761

zbMATH Keywords

Krohn-Rhodes complexitypseudoidentity basespseudovarieties of finite monoidswreath products

Mathematics Subject Classification ID

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

Recommendations

• COMPLEXITY PSEUDOVARIETIES ARE NOT LOCAL: TYPE II SUBSEMIGROUPS CAN FALL ARBITRARILY IN COMPLEXITY
• scientific article; zbMATH DE number 1419247
• Krohn-Rhodes complexity of Brauer type semigroups.
• Congruences on the Lattice of Pseudovarieties of Finite Semigroups
• Subsemigroups and complexity via the presentation lemma

Cites work

• A reduction theorem for complexity of finite semigroups
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART I
• Complexity of finite semigroups
• COMPLEXITY PSEUDOVARIETIES ARE NOT LOCAL: TYPE II SUBSEMIGROUPS CAN FALL ARBITRARILY IN COMPLEXITY
• Decomposition and complexity of finite semigroups
• Group-complexity and reversals of finite semigroups
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 798167 (Why is no real title available?)
• HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
• IDEMPOTENT POINTLIKE SETS
• Improved lower bounds for the complexity of finite semigroups
• INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES
• Infinite iteration of matrix semigroups. I: Structure theorem for torsion semigroups
• Infinite iteration of matrix semigroups. II: Structure theorem for arbitrary semigroups up to aperiodic morphism
• Kernel systems - a global study of homomorphisms on finite semigroups
• Lower bounds for complexity of finite semigroups
• On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties.
• On aperiodic relational morphisms.
• On finite 0-simple semigroups and graph theory
• On The Profinite Topology on a Free Group
• STABLE PAIRS
• Subsemigroups and complexity via the presentation lemma
• The fundamental lemma of complexity for arbitrary finite semigroups

Cited in

(4)

• 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
• Degree 2 transformation semigroups as continuous maps on graphs: Complexity and examples

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4680740)