Krohn-Rhodes complexity pseudovarieties are not finitely based
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.

DOI : 10.1051/ita:2005016
Classification : 20M07
Mots-clés : complexity, finite basis problem, the presentation lemma
@article{ITA_2005__39_1_279_0,
     author = {Rhodes, John and Steinberg, Benjamin},
     title = {Krohn-Rhodes complexity pseudovarieties are not finitely based},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {279--296},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {1},
     year = {2005},
     doi = {10.1051/ita:2005016},
     mrnumber = {2132592},
     zbl = {1083.20050},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2005016/}
}
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
SP  - 279
EP  - 296
VL  - 39
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2005016/
DO  - 10.1051/ita:2005016
LA  - en
ID  - ITA_2005__39_1_279_0
ER  - 
%0 Journal Article
%A Rhodes, John
%A Steinberg, Benjamin
%T Krohn-Rhodes complexity pseudovarieties are not finitely based
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2005
%P 279-296
%V 39
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2005016/
%R 10.1051/ita:2005016
%G en
%F ITA_2005__39_1_279_0
Rhodes, John; Steinberg, Benjamin. Krohn-Rhodes complexity pseudovarieties are not finitely based. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 279-296. doi : 10.1051/ita:2005016. http://archive.numdam.org/articles/10.1051/ita:2005016/

[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

Cité par Sources :