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), p. 279-296 / Harvested from Numdam

Résumé

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

Détail

Publié le : 2005-01-01

MR 2132592 | Zbl 1083.20050

DOI : https://doi.org/10.1051/ita:2005016
Classification:  20M07

Bibliographie

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

[2] J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products. Internat. J. Algebra Comput. 9 (1999) 241-261. | Zbl 1028.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. | Zbl 0722.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. | Zbl 0836.20081

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

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

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

[8] K. Henckell, Stable pairs. Internat. J. Algebra Comput. (Submitted). | Zbl 1209.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. | Zbl 0791.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. | Zbl 0148.01002

[11] K. Krohn and J. Rhodes, Complexity of finite semigroups. Ann. Math. 88 (1968) 128-160. | Zbl 0162.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). | MR 912694 | Zbl 0632.68069

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

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

[16] J. Rhodes, Infinite iteration of matrix semigroups. I. Structure theorem for torsion semigroups. J. Algebra 98 (1986) 422-451. | Zbl 0584.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. | Zbl 0626.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). | MR 2258836 | Zbl 1105.20049

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

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

[21] J. Rhodes and B. Tilson, A reduction theorem for complexity of finite semigroups. Semigroup Forum 10 (1975) 96-114. | Zbl 0303.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. | Zbl 0811.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. | Zbl 1048.20037

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

[26] B. Tilson, Decomposition and complexity of finite semigroups. Semigroup Forum 3 (1971) 189-250. | Zbl 0226.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].

[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 0338.20085