The pseudovariety of semigroups of triangular matrices over a finite field

Jorge Almeida; Stuart W. Margolis; Mikhail V. Volkov

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 39, Issue: 1, page 31-48
  • ISSN: 0988-3754

Abstract

top
We show that semigroups representable by triangular matrices over a fixed finite field form a decidable pseudovariety and provide a finite pseudoidentity basis for it.

How to cite

top

Almeida, Jorge, Margolis, Stuart W., and Volkov, Mikhail V.. "The pseudovariety of semigroups of triangular matrices over a finite field." RAIRO - Theoretical Informatics and Applications 39.1 (2010): 31-48. <http://eudml.org/doc/92764>.

@article{Almeida2010,
abstract = { We show that semigroups representable by triangular matrices over a fixed finite field form a decidable pseudovariety and provide a finite pseudoidentity basis for it. },
author = {Almeida, Jorge, Margolis, Stuart W., Volkov, Mikhail V.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {triangular matrix semigroups; pseudovarieties; finite semigroups; semigroups representable by upper triangular matrices; finite pseudoidentity bases},
language = {eng},
month = {3},
number = {1},
pages = {31-48},
publisher = {EDP Sciences},
title = {The pseudovariety of semigroups of triangular matrices over a finite field},
url = {http://eudml.org/doc/92764},
volume = {39},
year = {2010},
}

TY - JOUR
AU - Almeida, Jorge
AU - Margolis, Stuart W.
AU - Volkov, Mikhail V.
TI - The pseudovariety of semigroups of triangular matrices over a finite field
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 39
IS - 1
SP - 31
EP - 48
AB - We show that semigroups representable by triangular matrices over a fixed finite field form a decidable pseudovariety and provide a finite pseudoidentity basis for it.
LA - eng
KW - triangular matrix semigroups; pseudovarieties; finite semigroups; semigroups representable by upper triangular matrices; finite pseudoidentity bases
UR - http://eudml.org/doc/92764
ER -

References

top
  1. J. Almeida, Implicit operations on finite J-trivial semigroups and a conjecture of I. Simon. J. Pure Appl. Algebra69 (1990) 205–218.  Zbl0724.08003
  2. J. Almeida, Finite Semigroups and Universal Algebra. World Scientific (1995).  Zbl0757.08001
  3. J. Almeida and A. Azevedo, Globals of pseudovarieties of commutative semigroups: the finite basis problem, decidability, and gaps. Proc. Edinburgh Math. Soc.44 (2001) 27–47.  Zbl0993.20035
  4. J. Almeida and M.V. Volkov, Profinite identities for finite semigroups whose subgroups belong to a given pseudovariety. J. Algebra Appl.2 (2003) 137–163.  Zbl1061.20050
  5. A.H. Clifford and G.B. Preston, The Algebraic Theory of Semigroups. Amer. Math. Soc. Vol. I (1961); Vol. II (1967).  Zbl0111.03403
  6. R.S. Cohen and J.A. Brzozowski, Dot-depth of star-free events. J. Comp. Syst. Sci.5 (1971) 1–15.  Zbl0217.29602
  7. S. Eilenberg, Automata, Languages and Machines. Academic Press, Vol. A (1974); Vol. B (1976).  Zbl0317.94045
  8. S. Eilenberg and M.P. Schützenberger, On pseudovarieties. Adv. Math.19 (1976) 413–418.  Zbl0351.20035
  9. D. Gorenstein, Finite Groups. 2nd edition, Chelsea Publishing Company (1980).  
  10. R.M. Guralnick, Triangularization of sets of matrices. Linear Multilinear Algebra9 (1980) 133–140.  Zbl0443.15006
  11. K. Henckell and J.-E. Pin, Ordered monoids and J-trivial monoids, in Algorithmic problems in groups and semigroups, edited by J.-C. Birget, S. Margolis, J. Meakin and M. Sapir. Birkhäuser (2000) 121–137.  Zbl0946.20031
  12. P. Higgins, A proof of Simon's theorem on piecewise testable languages. Theor. Comp. Sci.178 (1997) 257–264.  Zbl0901.68093
  13. E.R. Kolchin, On certain concepts in the theory of algebraic matrix groups. Ann. Math.49 (1948) 774–789.  Zbl0037.18801
  14. G. Lallement, Semigroups and Combinatorial Applications. John Wiley & Sons (1979).  Zbl0421.20025
  15. H. Neumann, Varieties of groups. Springer-Verlag (1967).  Zbl0149.26704
  16. J. Okniński, Semigroup of Matrices. World Scientific (1998).  Zbl0911.20042
  17. J.-E. Pin, Variétés de langages formels. Masson, 1984 [French; Engl. translation: Varieties of formal languages. North Oxford Academic (1986) and Plenum (1986)].  
  18. J.-E. Pin and H. Straubing, Monoids of upper triangular matrices, in Semigroups. Structure and Universal Algebraic Problems, edited by G. Pollák, Št. Schwarz and O. Steinfeld. Colloquia Mathematica Societatis János Bolyai39, North-Holland (1985) 259–272.  
  19. H. Radjavi and P. Rosenthal, Simultaneous Triangularization. Springer-Verlag (2000).  Zbl0981.15007
  20. J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis14 (1982) 1–10.  Zbl0484.08007
  21. I. Simon, Hierarchies of Events of Dot-Depth One. Ph.D. Thesis, University of Waterloo (1972).  
  22. I. Simon, Piecewise testable events, in Proc. 2nd GI Conf.Lect. Notes Comp. Sci.33 (1975) 214–222.  Zbl0316.68034
  23. J. Stern, Characterization of some classes of regular events. Theor. Comp. Sci.35 (1985) 17–42.  Zbl0604.68066
  24. H. Straubing, On finite J-trivial monoids. Semigroup Forum19 (1980) 107–110.  Zbl0435.20036
  25. H. Straubing, Finite semigroup varieties of the form V ∗ D. J. Pure Appl. Algebra36 (1985) 53–94.  Zbl0561.20042
  26. H. Straubing and D. Thérien, Partially ordered finite monoids and a theorem of I. Simon. J. Algebra119 (1988) 393–399.  Zbl0658.20035
  27. D. Thérien, Classification of finite monoids: the language approach. Theor. Comp. Sci.14 (1981) 195–208.  Zbl0471.20055
  28. D. Thérien, Subword counting and nilpotent groups, in Combinatorics on Words, Progress and Perspectives, edited by L.J. Cummings. Academic Press (1983) 297–305.  Zbl0572.20052
  29. M.V. Volkov, On a class of semigroup pseudovarieties without finite pseudoidentity basis. Int. J. Algebra Computation5 (1995) 127–135.  Zbl0834.20058
  30. M.V. Volkov and I.A. Goldberg, Identities of semigroups of triangular matrices over finite fields. Mat. Zametki73 (2003) 502–510 [Russian; Engl. translation: Math. Notes73 (2003) 474–481].  

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.