The pseudovariety of semigroups of triangular matrices over a finite field
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 39 (2005) no. 1, p. 31-48

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.

DOI : https://doi.org/10.1051/ita:2005002
Classification:  20M07,  20M030
@article{ITA_2005__39_1_31_0,
author = {Almeida, Jorge and Margolis, Stuart W. and Volkov, Mikhail V.},
title = {The pseudovariety of semigroups of triangular matrices over a finite field},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
publisher = {EDP-Sciences},
volume = {39},
number = {1},
year = {2005},
pages = {31-48},
doi = {10.1051/ita:2005002},
zbl = {1086.20029},
mrnumber = {2132577},
language = {en},
url = {http://www.numdam.org/item/ITA_2005__39_1_31_0}
}

Almeida, Jorge; Margolis, Stuart W.; Volkov, Mikhail V. The pseudovariety of semigroups of triangular matrices over a finite field. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 39 (2005) no. 1, pp. 31-48. doi : 10.1051/ita:2005002. http://www.numdam.org/item/ITA_2005__39_1_31_0/

[1] J. Almeida, Implicit operations on finite $J$-trivial semigroups and a conjecture of I. Simon. J. Pure Appl. Algebra 69 (1990) 205-218. | Zbl 0724.08003

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

[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. | Zbl 0993.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. | Zbl 1061.20050

[5] A.H. Clifford and G.B. Preston, The Algebraic Theory of Semigroups. Amer. Math. Soc. Vol. I (1961); Vol. II (1967). | Zbl 0111.03403

[6] R.S. Cohen and J.A. Brzozowski, Dot-depth of star-free events. J. Comp. Syst. Sci. 5 (1971) 1-15. | Zbl 0217.29602

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

[8] S. Eilenberg and M.P. Schützenberger, On pseudovarieties. Adv. Math. 19 (1976) 413-418. | Zbl 0351.20035

[9] D. Gorenstein, Finite Groups. 2nd edition, Chelsea Publishing Company (1980). | MR 569209 | Zbl 0463.20012

[10] R.M. Guralnick, Triangularization of sets of matrices. Linear Multilinear Algebra 9 (1980) 133-140. | Zbl 0443.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. | Zbl 0946.20031

[12] P. Higgins, A proof of Simon's theorem on piecewise testable languages. Theor. Comp. Sci. 178 (1997) 257-264. | Zbl 0901.68093

[13] E.R. Kolchin, On certain concepts in the theory of algebraic matrix groups. Ann. Math. 49 (1948) 774-789. | Zbl 0037.18801

[14] G. Lallement, Semigroups and Combinatorial Applications. John Wiley & Sons (1979). | MR 530552 | Zbl 0421.20025

[15] H. Neumann, Varieties of groups. Springer-Verlag (1967). | MR 215899 | Zbl 0251.20001

[16] J. Okniński, Semigroup of Matrices. World Scientific (1998). | MR 1785162

[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)]. | MR 752695 | Zbl 0636.68093

[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 Bolyai 39, North-Holland (1985) 259-272. | Zbl 0635.20028

[19] H. Radjavi and P. Rosenthal, Simultaneous Triangularization. Springer-Verlag (2000). | MR 1736065 | Zbl 0981.15007

[20] J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1-10. | Zbl 0484.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. | Zbl 0316.68034

[23] J. Stern, Characterization of some classes of regular events. Theor. Comp. Sci. 35 (1985) 17-42. | Zbl 0604.68066

[24] H. Straubing, On finite $J$-trivial monoids. Semigroup Forum 19 (1980) 107-110. | Zbl 0435.20036

[25] H. Straubing, Finite semigroup varieties of the form $𝐕*𝐃$. J. Pure Appl. Algebra 36 (1985) 53-94. | Zbl 0561.20042

[26] H. Straubing and D. Thérien, Partially ordered finite monoids and a theorem of I. Simon. J. Algebra 119 (1988) 393-399. | Zbl 0658.20035

[27] D. Thérien, Classification of finite monoids: the language approach. Theor. Comp. Sci. 14 (1981) 195-208. | Zbl 0471.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. | Zbl 0572.20052

[29] M.V. Volkov, On a class of semigroup pseudovarieties without finite pseudoidentity basis. Int. J. Algebra Computation 5 (1995) 127-135. | Zbl 0834.20058

[30] M.V. Volkov and I.A. Goldberg, Identities of semigroups of triangular matrices over finite fields. Mat. Zametki 73 (2003) 502-510 [Russian; Engl. translation: Math. Notes 73 (2003) 474-481]. | Zbl 1064.20056