The pseudovariety of semigroups of triangular matrices over a finite field

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

doi:10.1051/ita:2005002

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 31-48

Résumé

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.

MR Zbl

DOI : 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},
     pages = {31--48},
     year = {2005},
     publisher = {EDP Sciences},
     volume = {39},
     number = {1},
     doi = {10.1051/ita:2005002},
     mrnumber = {2132577},
     zbl = {1086.20029},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita:2005002/}
}

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 - Informatique Théorique et Applications
PY  - 2005
SP  - 31
EP  - 48
VL  - 39
IS  - 1
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ita:2005002/
DO  - 10.1051/ita:2005002
LA  - en
ID  - ITA_2005__39_1_31_0
ER  -

%0 Journal Article
%A Almeida, Jorge
%A Margolis, Stuart W.
%A Volkov, Mikhail V.
%T The pseudovariety of semigroups of triangular matrices over a finite field
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2005
%P 31-48
%V 39
%N 1
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ita:2005002/
%R 10.1051/ita:2005002
%G en
%F 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, Tome 39 (2005) no. 1, pp. 31-48. doi: 10.1051/ita:2005002

Bibliographie
Cité par

[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

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

[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

[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

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

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

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

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

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

[10] R.M. Guralnick, Triangularization of sets of matrices. Linear Multilinear Algebra 9 (1980) 133-140. | Zbl

[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

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

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

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

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

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

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

[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

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

[20] J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1-10. | Zbl

[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

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

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

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

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

[27] D. Thérien, Classification of finite monoids: the language approach. Theor. Comp. Sci. 14 (1981) 195-208. | Zbl

[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

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

[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

Cité par Sources :