Krohn-Rhodes complexity pseudovarieties are not finitely based

Rhodes, John; Steinberg, Benjamin

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 279-296.

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$.

Classification : 20M07
Mots clés : complexity, finite basis problem, the presentation lemma

[1] J. Almeida, Finite Semigroups and Universal Algebra. World Scientific, Singapore (1994). | MR | Zbl

[2] J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products. Internat. J. Algebra Comput. 9 (1999) 241-261. | Zbl

[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. | Zbl

[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. | Zbl

[5] S. Eilenberg, Automata, Languages and Machines. Academic Press, New York, Vol. A (1974); Vol. B (1976). | Zbl

[6] R.L. Graham, On finite 0-simple semigroups and graph theory. Math. Syst. Theor. 2 (1968) 325-339. | Zbl

[7] K. Henckell, Idempotent pointlikes. Internat. J. Algebra Comput. (To appear). | MR | Zbl

[8] K. Henckell, Stable pairs. Internat. J. Algebra Comput. (Submitted). | Zbl

[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. | Zbl

[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. | Zbl

[11] K. Krohn and J. Rhodes, Complexity of finite semigroups. Ann. Math. 88 (1968) 128-160. | Zbl

[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). | MR | Zbl

[14] J. Rhodes, The fundamental lemma of complexity for arbitrary finite semigroups. Bull. Amer. Math. Soc. 74 (1968) 1104-1109. | Zbl

[15] J. Rhodes, Kernel systems - A global study of homomorphisms on finite semigroups. J. Algebra 49 (1977) 1-45. | Zbl

[16] J. Rhodes, Infinite iteration of matrix semigroups. I. Structure theorem for torsion semigroups. J. Algebra 98 (1986) 422-451. | Zbl

[17] J. Rhodes, Infinite iteration of matrix semigroups. II. Structure theorem for arbitrary semigroups up to aperiodic morphism. J. Algebra 100 (1986) 25-137. | Zbl

[18] J. Rhodes and B. Steinberg, Complexity pseudovarieties are not local; type II subsemigroups can fall arbitrarily in complexity. Internat. J. Algebra Comput. (Submitted). | MR | Zbl

[19] J. Rhodes and B. Tilson, Lower bounds for complexity of finite semigroups. J. Pure Appl. Algebra 1 (1971) 79-95. | Zbl

[20] J. Rhodes and B. Tilson, Improved lower bounds for the complexity of finite semigroups. J. Pure Appl. Algebra 2 (1972) 13-71. | Zbl

[21] J. Rhodes and B. Tilson, A reduction theorem for complexity of finite semigroups. Semigroup Forum 10 (1975) 96-114. | Zbl

[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. | Zbl

[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. | Zbl

[25] B. Steinberg, On aperiodic relational morphisms. Semigroup Forum. (Accepted). | MR | Zbl

[26] B. Tilson, Decomposition and complexity of finite semigroups. Semigroup Forum 3 (1971) 189-250. | Zbl

[27] B. Tilson, Complexity of two-$𝒥$-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].

[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. | Zbl