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

Abstract

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

How to cite

top

Rhodes, 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&gt;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&gt;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. [1] J. Almeida, Finite Semigroups and Universal Algebra. World Scientific, Singapore (1994). Zbl0844.20039MR1331143
  2. [2] J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products. Internat. J. Algebra Comput. 9 (1999) 241–261. Zbl1028.20038
  3. [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. [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. [5] S. Eilenberg, Automata, Languages and Machines. Academic Press, New York, Vol. A (1974); Vol. B (1976). Zbl0317.94045
  6. [6] R.L. Graham, On finite 0-simple semigroups and graph theory. Math. Syst. Theor. 2 (1968) 325–339. Zbl0177.03103
  7. [7] K. Henckell, Idempotent pointlikes. Internat. J. Algebra Comput. (To appear). Zbl1080.20054MR2104776
  8. [8] K. Henckell, Stable pairs. Internat. J. Algebra Comput. (Submitted). Zbl1209.20051
  9. [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. [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. [11] K. Krohn and J. Rhodes, Complexity of finite semigroups. Ann. Math. 88 (1968) 128–160. Zbl0162.03902
  12. [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. [13] J.-E. Pin, Varieties of Formal Languages. Plenum, New York (1986). Zbl0632.68069MR912694
  14. [14] J. Rhodes, The fundamental lemma of complexity for arbitrary finite semigroups. Bull. Amer. Math. Soc. 74 (1968) 1104–1109. Zbl0185.04801
  15. [15] J. Rhodes, Kernel systems – A global study of homomorphisms on finite semigroups. J. Algebra 49 (1977) 1–45. Zbl0379.20054
  16. [16] J. Rhodes, Infinite iteration of matrix semigroups. I. Structure theorem for torsion semigroups. J. Algebra 98 (1986) 422–451. Zbl0584.20053
  17. [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. [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. [19] J. Rhodes and B. Tilson, Lower bounds for complexity of finite semigroups. J. Pure Appl. Algebra 1 (1971) 79–95. Zbl0259.20051
  20. [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. [21] J. Rhodes and B. Tilson, A reduction theorem for complexity of finite semigroups. Semigroup Forum 10 (1975) 96–114. Zbl0303.20042
  22. [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. [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. [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. [25] B. Steinberg, On aperiodic relational morphisms. Semigroup Forum. (Accepted). Zbl1140.20044MR2107191
  26. [26] B. Tilson, Decomposition and complexity of finite semigroups. Semigroup Forum 3 (1971) 189–250. Zbl0226.20060
  27. [27] B. Tilson, Complexity of two- 𝒥 -class semigroups. Adv. Math. 11 (1973) 215–237. 
  28. [28] B. Tilson, Depth decomposition theorem. Chapter XI in [5]. 
  29. [29] B. Tilson, Complexity of semigroups and morphisms. Chapter XII in [5]. Zbl0226.20060
  30. [30] B. Tilson, Presentation lemma... the short form. (Unpublished 1995). 
  31. [31] Y. Zalcstein, Group-complexity and reversals of finite semigroups. Math. Syst. Theor. 8 (1974/75) 235–242. Zbl0338.20085

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.