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).  
  2. J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products. Internat. J. Algebra Comput.9 (1999) 241–261.  
  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.  
  4. B. Austin, K. Henckell, C. Nehaniv and J. Rhodes, Subsemigroups and complexity via the presentation lemma. J. Pure Appl. Algebra101 (1995) 245–289.  
  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.  
  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.  
  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.  
  11. K. Krohn and J. Rhodes, Complexity of finite semigroups. Ann. Math.88 (1968) 128–160.  
  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.  
  15. J. Rhodes, Kernel systems – A global study of homomorphisms on finite semigroups. J. Algebra49 (1977) 1–45.  
  16. J. Rhodes, Infinite iteration of matrix semigroups. I. Structure theorem for torsion semigroups. J. Algebra98 (1986) 422–451.  
  17. J. Rhodes, Infinite iteration of matrix semigroups. II. Structure theorem for arbitrary semigroups up to aperiodic morphism. J. Algebra100 (1986) 25–137.  
  18. J. Rhodes and B. Steinberg, Complexity pseudovarieties are not local; type II subsemigroups can fall arbitrarily in complexity. Internat. J. Algebra Comput. (Submitted).  
  19. J. Rhodes and B. Tilson, Lower bounds for complexity of finite semigroups. J. Pure Appl. Algebra1 (1971) 79–95.  
  20. J. Rhodes and B. Tilson, Improved lower bounds for the complexity of finite semigroups. J. Pure Appl. Algebra2 (1972) 13–71.  
  21. J. Rhodes and B. Tilson, A reduction theorem for complexity of finite semigroups. Semigroup Forum10 (1975) 96–114.  
  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.  
  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.  
  25. B. Steinberg, On aperiodic relational morphisms. Semigroup Forum. (Accepted).  
  26. B. Tilson, Decomposition and complexity of finite semigroups. Semigroup Forum3 (1971) 189–250.  
  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.  
  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.  

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.