# Krohn-Rhodes complexity pseudovarieties are not finitely based

John Rhodes; Benjamin Steinberg

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

- 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 - Informatique Théorique et Applications 39.1 (2005): 279-296. <http://eudml.org/doc/245322>.

@article{Rhodes2005,

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 - Informatique Théorique et Applications},

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

language = {eng},

number = {1},

pages = {279-296},

publisher = {EDP-Sciences},

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

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

volume = {39},

year = {2005},

}

TY - JOUR

AU - Rhodes, John

AU - Steinberg, Benjamin

TI - Krohn-Rhodes complexity pseudovarieties are not finitely based

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2005

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/245322

ER -

## References

top- [1] J. Almeida, Finite Semigroups and Universal Algebra. World Scientific, Singapore (1994). Zbl0844.20039MR1331143
- [2] J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products. Internat. J. Algebra Comput. 9 (1999) 241–261. Zbl1028.20038
- [3] 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
- [4] B. Austin, K. Henckell, C. Nehaniv and J. Rhodes, Subsemigroups and complexity via the presentation lemma. J. Pure Appl. Algebra 101 (1995) 245–289. Zbl0836.20081
- [5] S. Eilenberg, Automata, Languages and Machines. Academic Press, New York, Vol. A (1974); Vol. B (1976). Zbl0317.94045
- [6] R.L. Graham, On finite 0-simple semigroups and graph theory. Math. Syst. Theor. 2 (1968) 325–339. Zbl0177.03103
- [7] K. Henckell, Idempotent pointlikes. Internat. J. Algebra Comput. (To appear). Zbl1080.20054MR2104776
- [8] K. Henckell, Stable pairs. Internat. J. Algebra Comput. (Submitted). Zbl1209.20051
- [9] 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
- [10] 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
- [11] K. Krohn and J. Rhodes, Complexity of finite semigroups. Ann. Math. 88 (1968) 128–160. Zbl0162.03902
- [12] 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).
- [13] J.-E. Pin, Varieties of Formal Languages. Plenum, New York (1986). Zbl0632.68069MR912694
- [14] J. Rhodes, The fundamental lemma of complexity for arbitrary finite semigroups. Bull. Amer. Math. Soc. 74 (1968) 1104–1109. Zbl0185.04801
- [15] J. Rhodes, Kernel systems – A global study of homomorphisms on finite semigroups. J. Algebra 49 (1977) 1–45. Zbl0379.20054
- [16] J. Rhodes, Infinite iteration of matrix semigroups. I. Structure theorem for torsion semigroups. J. Algebra 98 (1986) 422–451. Zbl0584.20053
- [17] J. Rhodes, Infinite iteration of matrix semigroups. II. Structure theorem for arbitrary semigroups up to aperiodic morphism. J. Algebra 100 (1986) 25–137. Zbl0626.20050
- [18] J. Rhodes and B. Steinberg, Complexity pseudovarieties are not local; type II subsemigroups can fall arbitrarily in complexity. Internat. J. Algebra Comput. (Submitted). Zbl1105.20049MR2258836
- [19] J. Rhodes and B. Tilson, Lower bounds for complexity of finite semigroups. J. Pure Appl. Algebra 1 (1971) 79–95. Zbl0259.20051
- [20] J. Rhodes and B. Tilson, Improved lower bounds for the complexity of finite semigroups. J. Pure Appl. Algebra 2 (1972) 13–71. Zbl0257.20059
- [21] J. Rhodes and B. Tilson, A reduction theorem for complexity of finite semigroups. Semigroup Forum 10 (1975) 96–114. Zbl0303.20042
- [22] 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.
- [23] L. Ribes and P.A. Zalesskiĭ, On the profinite topology on a free group. Bull. London Math. Soc. 25 (1993) 37–43. Zbl0811.20026
- [24] B. Steinberg, On an assertion of J. Rhodes and the finite basis and finite vertex rank problems for pseudovarieties. J. Pure Appl. Algebra 186 (2004) 91–107. Zbl1048.20037
- [25] B. Steinberg, On aperiodic relational morphisms. Semigroup Forum. (Accepted). Zbl1140.20044MR2107191
- [26] B. Tilson, Decomposition and complexity of finite semigroups. Semigroup Forum 3 (1971) 189–250. Zbl0226.20060
- [27] B. Tilson, Complexity of two-$\mathcal{J}$-class semigroups. Adv. Math. 11 (1973) 215–237.
- [28] B. Tilson, Depth decomposition theorem. Chapter XI in [5].
- [29] B. Tilson, Complexity of semigroups and morphisms. Chapter XII in [5]. Zbl0226.20060
- [30] B. Tilson, Presentation lemma... the short form. (Unpublished 1995).
- [31] 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.