# Krohn-Rhodes complexity pseudovarieties are not finitely based

John Rhodes; Benjamin Steinberg

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 39, Issue: 1, page 279-296
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topRhodes, John, and Steinberg, Benjamin. "Krohn-Rhodes complexity pseudovarieties are not finitely based." RAIRO - Theoretical Informatics and Applications 39.1 (2010): 279-296. <http://eudml.org/doc/92761>.

@article{Rhodes2010,

abstract = { We prove that the pseudovariety of monoids of Krohn-Rhodes
complexity at most n is not finitely based for all n>0. More
specifically, for each pair of positive integers n,k, we
construct a monoid of complexity n+1, all of whose k-generated
submonoids have complexity at most n. },

author = {Rhodes, John, Steinberg, Benjamin},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Complexity; finite basis problem; the presentation
lemma; pseudovarieties of finite monoids; pseudoidentity bases; wreath products; Krohn-Rhodes complexity},

language = {eng},

month = {3},

number = {1},

pages = {279-296},

publisher = {EDP Sciences},

title = {Krohn-Rhodes complexity pseudovarieties are not finitely based},

url = {http://eudml.org/doc/92761},

volume = {39},

year = {2010},

}

TY - JOUR

AU - Rhodes, John

AU - Steinberg, Benjamin

TI - Krohn-Rhodes complexity pseudovarieties are not finitely based

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 39

IS - 1

SP - 279

EP - 296

AB - We prove that the pseudovariety of monoids of Krohn-Rhodes
complexity at most n is not finitely based for all n>0. More
specifically, for each pair of positive integers n,k, we
construct a monoid of complexity n+1, all of whose k-generated
submonoids have complexity at most n.

LA - eng

KW - Complexity; finite basis problem; the presentation
lemma; pseudovarieties of finite monoids; pseudoidentity bases; wreath products; Krohn-Rhodes complexity

UR - http://eudml.org/doc/92761

ER -

## References

top- J. Almeida, Finite Semigroups and Universal Algebra. World Scientific, Singapore (1994). Zbl0844.20039
- J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products. Internat. J. Algebra Comput.9 (1999) 241–261. Zbl1028.20038
- C.J. Ash, Inevitable graphs: A proof of the Type II conjecture and some related decision procedures. Internat. J. Algebra Comput.1 (1991) 127–146. Zbl0722.20039
- B. Austin, K. Henckell, C. Nehaniv and J. Rhodes, Subsemigroups and complexity via the presentation lemma. J. Pure Appl. Algebra101 (1995) 245–289. Zbl0836.20081
- S. Eilenberg, Automata, Languages and Machines. Academic Press, New York, Vol. A (1974); Vol. B (1976).
- R.L. Graham, On finite 0-simple semigroups and graph theory. Math. Syst. Theor.2 (1968) 325–339. Zbl0177.03103
- K. Henckell, Idempotent pointlikes. Internat. J. Algebra Comput. (To appear).
- K. Henckell, Stable pairs. Internat. J. Algebra Comput. (Submitted).
- K. Henckell, S. Margolis, J.-E. Pin and J. Rhodes, Ash's type II Theorem, profinite topology and Mal'cev products: Part I. Internat. J. Algebra Comput.1 (1991) 411–436. Zbl0791.20079
- K. Krohn and J. Rhodes, Algebraic theory of machines, I: Prime decomposition theorem for finite semigroups and machines. Trans. Amer. Math. Soc.116 (1965) 450–464. Zbl0148.01002
- K. Krohn and J. Rhodes, Complexity of finite semigroups. Ann. Math.88 (1968) 128–160. Zbl0162.03902
- K. Krohn, J. Rhodes and B. Tilson, Lectures on the algebraic theory of finite semigroups and finite-state machines Chapters 1, 5–9 (Chapter 6 with M.A. Arbib), in The Algebraic Theory of Machines, Languages, and Semigroups, edited by M.A. Arbib. Academic Press, New York (1968).
- J.-E. Pin, Varieties of Formal Languages. Plenum, New York (1986).
- J. Rhodes, The fundamental lemma of complexity for arbitrary finite semigroups. Bull. Amer. Math. Soc.74 (1968) 1104–1109. Zbl0185.04801
- J. Rhodes, Kernel systems – A global study of homomorphisms on finite semigroups. J. Algebra49 (1977) 1–45. Zbl0379.20054
- J. Rhodes, Infinite iteration of matrix semigroups. I. Structure theorem for torsion semigroups. J. Algebra98 (1986) 422–451. Zbl0584.20053
- J. Rhodes, Infinite iteration of matrix semigroups. II. Structure theorem for arbitrary semigroups up to aperiodic morphism. J. Algebra100 (1986) 25–137. Zbl0626.20050
- J. Rhodes and B. Steinberg, Complexity pseudovarieties are not local; type II subsemigroups can fall arbitrarily in complexity. Internat. J. Algebra Comput. (Submitted). Zbl1105.20049
- J. Rhodes and B. Tilson, Lower bounds for complexity of finite semigroups. J. Pure Appl. Algebra1 (1971) 79–95. Zbl0259.20051
- J. Rhodes and B. Tilson, Improved lower bounds for the complexity of finite semigroups. J. Pure Appl. Algebra2 (1972) 13–71. Zbl0257.20059
- J. Rhodes and B. Tilson, A reduction theorem for complexity of finite semigroups. Semigroup Forum10 (1975) 96–114. Zbl0303.20042
- J. Rhodes and B. Tilson, Local complexity of finite semigroups, in Algebra, Topology, and Category Theory (collection of papers in honor of Samuel Eilenberg). Academic Press, New York (1976) 149–168.
- L. Ribes and P.A. Zalesskiĭ, On the profinite topology on a free group. Bull. London Math. Soc.25 (1993) 37–43. Zbl0811.20026
- B. Steinberg, On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties. J. Pure Appl. Algebra186 (2004) 91–107. Zbl1048.20037
- B. Steinberg, On aperiodic relational morphisms. Semigroup Forum. (Accepted). Zbl1140.20044
- B. Tilson, Decomposition and complexity of finite semigroups. Semigroup Forum3 (1971) 189–250. Zbl0226.20060
- B. Tilson, Complexity of two-$\mathcal{J}$-class semigroups. Adv. Math.11 (1973) 215–237.
- B. Tilson, Depth decomposition theorem. Chapter XI in [5]SS. Zbl0226.20060
- B. Tilson, Complexity of semigroups and morphisms. Chapter XII in [5]. Zbl0226.20060
- B. Tilson, Presentation lemma... the short form. (Unpublished 1995).
- Y. Zalcstein, Group-complexity and reversals of finite semigroups. Math. Syst. Theor.8 (1974/75) 235–242. Zbl0338.20085

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.