Krohn-Rhodes complexity pseudovarieties are not finitely based

John Rhodes; Benjamin Steinberg

RAIRO - Theoretical Informatics and Applications (2010)

  • 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 39.1 (2010): 279-296. <http://eudml.org/doc/92761>.

@article{Rhodes2010,
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},
keywords = {Complexity; finite basis problem; the presentation lemma; pseudovarieties of finite monoids; pseudoidentity bases; wreath products; Krohn-Rhodes complexity},
language = {eng},
month = {3},
number = {1},
pages = {279-296},
publisher = {EDP Sciences},
title = {Krohn-Rhodes complexity pseudovarieties are not finitely based},
url = {http://eudml.org/doc/92761},
volume = {39},
year = {2010},
}

TY - JOUR
AU - Rhodes, John
AU - Steinberg, Benjamin
TI - Krohn-Rhodes complexity pseudovarieties are not finitely based
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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/92761
ER -

References

top
  1. J. Almeida, Finite Semigroups and Universal Algebra. World Scientific, Singapore (1994).  Zbl0844.20039
  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. Algebra101 (1995) 245–289.  Zbl0836.20081
  5. S. Eilenberg, Automata, Languages and Machines. Academic Press, New York, Vol. A (1974); Vol. B (1976).  
  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).  
  8. K. Henckell, Stable pairs. Internat. J. Algebra Comput. (Submitted).  
  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).  
  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. Algebra49 (1977) 1–45.  Zbl0379.20054
  16. J. Rhodes, Infinite iteration of matrix semigroups. I. Structure theorem for torsion semigroups. J. Algebra98 (1986) 422–451.  Zbl0584.20053
  17. J. Rhodes, Infinite iteration of matrix semigroups. II. Structure theorem for arbitrary semigroups up to aperiodic morphism. J. Algebra100 (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.20049
  19. J. Rhodes and B. Tilson, Lower bounds for complexity of finite semigroups. J. Pure Appl. Algebra1 (1971) 79–95.  Zbl0259.20051
  20. J. Rhodes and B. Tilson, Improved lower bounds for the complexity of finite semigroups. J. Pure Appl. Algebra2 (1972) 13–71.  Zbl0257.20059
  21. J. Rhodes and B. Tilson, A reduction theorem for complexity of finite semigroups. Semigroup Forum10 (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. Algebra186 (2004) 91–107.  Zbl1048.20037
  25. B. Steinberg, On aperiodic relational morphisms. Semigroup Forum. (Accepted).  Zbl1140.20044
  26. B. Tilson, Decomposition and complexity of finite semigroups. Semigroup Forum3 (1971) 189–250.  Zbl0226.20060
  27. B. Tilson, Complexity of two- 𝒥 -class semigroups. Adv. Math.11 (1973) 215–237.  
  28. B. Tilson, Depth decomposition theorem. Chapter XI in [5]SS.  Zbl0226.20060
  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 ?

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.