Representation theory of finite semigroups, semigroup radicals and formal language theory

Almeida, Jorge; Margolis, Stuart; Steinberg, Benjamin; Volkov, Mikhail

doi:10.1090/S0002-9947-08-04712-0

Representation theory of finite semigroups, semigroup radicals and formal language theory
HTML articles powered by AMS MathViewer

by Jorge Almeida, Stuart Margolis, Benjamin Steinberg and Mikhail Volkov PDF

Trans. Amer. Math. Soc. 361 (2009), 1429-1461 Request permission

Abstract:

In this paper we characterize the congruence associated to the direct sum of all irreducible representations of a finite semigroup over an arbitrary field, generalizing results of Rhodes for the field of complex numbers. Applications are given to obtain many new results, as well as easier proofs of several results in the literature, involving: triangularizability of finite semigroups; which semigroups have (split) basic semigroup algebras, two-sided semidirect product decompositions of finite monoids; unambiguous products of rational languages; products of rational languages with counter; and Černý’s conjecture for an important class of automata.

References

Jorge Almeida, Finite semigroups and universal algebra, Series in Algebra, vol. 3, World Scientific Publishing Co., Inc., River Edge, NJ, 1994. Translated from the 1992 Portuguese original and revised by the author. MR 1331143
Jorge Almeida, A syntactical proof of locality of DA, Internat. J. Algebra Comput. 6 (1996), no. 2, 165–177. MR 1386073, DOI 10.1142/S021819679600009X
J. Almeida, S. W. Margolis, B. Steinberg and M. V. Volkov, Modular and threshold subword counting and matrix representations of finite monoids, in “Words 2005, $5^{th}$ International Conference on Words, 13–17 September 2005, Acts”, eds. S. Brlek, C. Reutenauer, Publications du Laboratoire de Combinatoire et d’ Informatique Mathématique, UQAM 36 (2005), 65–78.
Jorge Almeida, Stuart W. Margolis, and Mikhail V. Volkov, The pseudovariety of semigroups of triangular matrices over a finite field, Theor. Inform. Appl. 39 (2005), no. 1, 31–48. MR 2132577, DOI 10.1051/ita:2005002
J. Almeida, S. W. Margolis, B. Steinberg and M. V. Volkov, Characterization of group radicals with an application to Mal’cev products, in preparation.
D. S. Ananichev and M. V. Volkov, Some results on Černý type problems for transformation semigroups, Semigroups and languages, World Sci. Publ., River Edge, NJ, 2004, pp. 23–42. MR 2170751, DOI 10.1142/9789812702616_{0}002
F. Arnold, “A linear algebra approach to synchronizing automata”, Master’s Thesis, Carleton University, Ottawa, 2005.
Fredrick Arnold and Benjamin Steinberg, Synchronizing groups and automata, Theoret. Comput. Sci. 359 (2006), no. 1-3, 101–110. MR 2251603, DOI 10.1016/j.tcs.2006.02.003
K. Auinger and B. Steinberg, On the extension problem for partial permutations, Proc. Amer. Math. Soc. 131 (2003), no. 9, 2693–2703. MR 1974324, DOI 10.1090/S0002-9939-03-06860-6
Pat Bidigare, Phil Hanlon, and Dan Rockmore, A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements, Duke Math. J. 99 (1999), no. 1, 135–174. MR 1700744, DOI 10.1215/S0012-7094-99-09906-4
Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005. MR 2133266
Kenneth S. Brown, Semigroups, rings, and Markov chains, J. Theoret. Probab. 13 (2000), no. 3, 871–938. MR 1785534, DOI 10.1023/A:1007822931408
Kenneth S. Brown, Semigroup and ring theoretical methods in probability, Representations of finite dimensional algebras and related topics in Lie theory and geometry, Fields Inst. Commun., vol. 40, Amer. Math. Soc., Providence, RI, 2004, pp. 3–26. MR 2057147
Ján Černý, A remark on homogeneous experiments with finite automata, Mat.-Fyz. Časopis. Sloven. Akad. Vied. 14 (1964), 208–216 (Slovak, with English summary). MR 168429
A. H. Clifford, Matrix representations of completely simple semigroups, Amer. J. Math. 64 (1942), 327–342. MR 6551, DOI 10.2307/2371687
A. H. Clifford and G. B. Preston, The algebraic theory of semigroups. Vol. I, Mathematical Surveys, No. 7, American Mathematical Society, Providence, R.I., 1961. MR 0132791
L. Dubuc, Sur les automates circulaires et la conjecture de Černý, RAIRO Inform. Théor. Appl. 32 (1998), no. 1-3, 21–34 (French, with English and French summaries). MR 1657507, DOI 10.1051/ita/1998321-300211
Samuel Eilenberg, Automata, languages, and machines. Vol. A, Pure and Applied Mathematics, Vol. 58, Academic Press [Harcourt Brace Jovanovich, Publishers], New York, 1974. MR 0530382
Samuel Eilenberg and M. P. Schützenberger, On pseudovarieties, Advances in Math. 19 (1976), no. 3, 413–418. MR 401604, DOI 10.1016/0001-8708(76)90029-3
J. A. Green, On the structure of semigroups, Ann. of Math. (2) 54 (1951), 163–172. MR 42380, DOI 10.2307/1969317
R. L. Graham, On finite $0$-simple semigroups and graph theory, Math. Systems Theory 2 (1968), 325–339. MR 240228, DOI 10.1007/BF01703263
T. E. Hall, The radical of the algebra of any finite semigroup over any field, J. Austral. Math. Soc. 11 (1970), 350–352. MR 0268302
Jarkko Kari, Synchronizing finite automata on Eulerian digraphs, Theoret. Comput. Sci. 295 (2003), no. 1-3, 223–232. Mathematical foundations of computer science (Mariánské Lázně, 2001). MR 1964667, DOI 10.1016/S0304-3975(02)00405-X
Kenneth Krohn and John Rhodes, Complexity of finite semigroups, Ann. of Math. (2) 88 (1968), 128–160. MR 236294, DOI 10.2307/1970558
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) of “Algebraic Theory of Machines, Languages, and Semigroups”, ed. M. A. Arbib, Academic Press, New York, 1968.
Gérard Lallement and Mario Petrich, Irreducible matrix representations of finite semigroups, Trans. Amer. Math. Soc. 139 (1969), 393–412. MR 242973, DOI 10.1090/S0002-9947-1969-0242973-3
T. Y. Lam, A first course in noncommutative rings, 2nd ed., Graduate Texts in Mathematics, vol. 131, Springer-Verlag, New York, 2001. MR 1838439, DOI 10.1007/978-1-4419-8616-0
Donald B. McAlister, Representations of semigroups by linear transformations. I, II, Semigroup Forum 2 (1971), no. 3, 189–263; ibid. 2 (1971), no. 4, 283–320. MR 286910, DOI 10.1007/bf02572292
W. D. Munn, On semigroup algebras, Proc. Cambridge Philos. Soc. 51 (1955), 1–15. MR 66355, DOI 10.1017/s0305004100029868
W. D. Munn, Matrix representations of semigroups, Proc. Cambridge Philos. Soc. 53 (1957), 5–12. MR 82050, DOI 10.1017/s0305004100031935
W. D. Munn, The Jacobson radical of a band ring, Math. Proc. Cambridge Philos. Soc. 105 (1989), no. 2, 277–283. MR 974983, DOI 10.1017/S0305004100067761
Jan Okniński, Semigroup algebras, Monographs and Textbooks in Pure and Applied Mathematics, vol. 138, Marcel Dekker, Inc., New York, 1991. MR 1083356
Jan Okniński, Semigroups of matrices, Series in Algebra, vol. 6, World Scientific Publishing Co., Inc., River Edge, NJ, 1998. MR 1785162, DOI 10.1142/9789812816290
A. Ja. Ovsyannikov, O radikal’nosti fundamental’nykh idealov polugruppovykh kolec (On radical properties of augmentation ideals of semigroup rings), in “Issledovanija Algebraicheskikh Sistem po Svojstvam ikh Podsistem”, ed. L. N. Shevrin, Ural State University, 1985, 119–127 (in Russian).
Donald S. Passman, The algebraic structure of group rings, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1977. MR 0470211
Pierre Péladeau, Sur le produit avec compteur modulo un nombre premier, RAIRO Inform. Théor. Appl. 26 (1992), no. 6, 553–564 (French, with English and French summaries). MR 1195745, DOI 10.1051/ita/1992260605531
J.-E. Pin, Sur un cas particulier de la conjecture de Cerny, Automata, languages and programming (Fifth Internat. Colloq., Udine, 1978) Lecture Notes in Comput. Sci., vol. 62, Springer, Berlin-New York, 1978, pp. 345–352 (French). MR 520853
Jean-Eric Pin, Propriétés syntactiques du produit non ambigu, Automata, languages and programming (Proc. Seventh Internat. Colloq., Noordwijkerhout, 1980) Lecture Notes in Comput. Sci., vol. 85, Springer, Berlin-New York, 1980, pp. 483–499 (French). MR 589026
J.-E. Pin, On two combinatorial problems arising from automata theory, Combinatorial mathematics (Marseille-Luminy, 1981) North-Holland Math. Stud., vol. 75, North-Holland, Amsterdam, 1983, pp. 535–548. MR 841339
J.-E. Pin, Varieties of formal languages, Foundations of Computer Science, Plenum Publishing Corp., New York, 1986. With a preface by M.-P. Schützenberger; Translated from the French by A. Howie. MR 912694, DOI 10.1007/978-1-4613-2215-3
Jean-Eric Pin, Howard Straubing, and Denis Thérien, Locally trivial categories and unambiguous concatenation, J. Pure Appl. Algebra 52 (1988), no. 3, 297–311. MR 952084, DOI 10.1016/0022-4049(88)90097-7
Mohan S. Putcha, Linear algebraic monoids, London Mathematical Society Lecture Note Series, vol. 133, Cambridge University Press, Cambridge, 1988. MR 964690, DOI 10.1017/CBO9780511600661
Mohan S. Putcha, Complex representations of finite monoids, Proc. London Math. Soc. (3) 73 (1996), no. 3, 623–641. MR 1407463, DOI 10.1112/plms/s3-73.3.623
Mohan S. Putcha, Complex representations of finite monoids. II. Highest weight categories and quivers, J. Algebra 205 (1998), no. 1, 53–76. MR 1631310, DOI 10.1006/jabr.1997.7395
Mohan S. Putcha, Semigroups and weights for group representations, Proc. Amer. Math. Soc. 128 (2000), no. 10, 2835–2842. MR 1691001, DOI 10.1090/S0002-9939-00-05464-2
Mohan S. Putcha, Reciprocity in character theory of finite semigroups, J. Pure Appl. Algebra 163 (2001), no. 3, 339–351. MR 1852124, DOI 10.1016/S0022-4049(00)00162-6
Norman R. Reilly and Shuhua Zhang, Operators on the lattice of pseudovarieties of finite semigroups, Semigroup Forum 57 (1998), no. 2, 208–239. MR 1634711, DOI 10.1007/PL00005974
Lex E. Renner, Linear algebraic monoids, Encyclopaedia of Mathematical Sciences, vol. 134, Springer-Verlag, Berlin, 2005. Invariant Theory and Algebraic Transformation Groups, V. MR 2134980
Christophe Reutenauer, Sur les variétés de langages et de monoïdes, Theoretical computer science (Fourth GI Conf., Aachen, 1979) Lecture Notes in Comput. Sci., vol. 67, Springer, Berlin-New York, 1979, pp. 260–265 (French). MR 568110
John Rhodes, A homomorphism theorem for finite semigroups, Math. Systems Theory 1 (1967), 289–304. MR 223473, DOI 10.1007/BF01695164
John Rhodes, Characters and complexity of finite semigroups, J. Combinatorial Theory 6 (1969), 67–85. MR 236293
John Rhodes, Algebraic theory of finite semigroups. Structure numbers and structure theorems for finite semigroups, Semigroups (Proc. Sympos., Wayne State Univ., Detroit, Mich., 1968) Academic Press, New York, 1969, pp. 125–162. MR 0281817
John Rhodes, Undecidability, automata, and pseudovarieties of finite semigroups, Internat. J. Algebra Comput. 9 (1999), no. 3-4, 455–473. Dedicated to the memory of Marcel-Paul Schützenberger. MR 1723477, DOI 10.1142/S0218196799000278
John Rhodes and Bret Tilson, The kernel of monoid morphisms, J. Pure Appl. Algebra 62 (1989), no. 3, 227–268. MR 1026876, DOI 10.1016/0022-4049(89)90137-0
John Rhodes and Pascal Weil, Decomposition techniques for finite semigroups, using categories. I, II, J. Pure Appl. Algebra 62 (1989), no. 3, 269–284, 285–312. MR 1026877, DOI 10.1016/0022-4049(89)90138-2
John Rhodes and Yechezkel Zalcstein, Elementary representation and character theory of finite semigroups and its application, Monoids and semigroups with applications (Berkeley, CA, 1989) World Sci. Publ., River Edge, NJ, 1991, pp. 334–367. MR 1142387
M. P. Schützenberger, On finite monoids having only trivial subgroups, Information and Control 8 (1965), 190–194. MR 176883
M. P. Schützenberger, Sur le produit de concaténation non ambigu, Semigroup Forum 13 (1976/77), no. 1, 47–75 (French). MR 444824, DOI 10.1007/BF02194921
I. Simon, “Hierarchies of events of dot-depth one”, Ph. D. Thesis, University of Waterloo, 1972.
Imre Simon, Piecewise testable events, Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975), Lecture Notes in Comput. Sci., Vol. 33, Springer, Berlin, 1975, pp. 214–222. MR 0427498
Imre Simon, The product of rational languages, Automata, languages and programming (Lund, 1993) Lecture Notes in Comput. Sci., vol. 700, Springer, Berlin, 1993, pp. 430–444. MR 1252424, DOI 10.1007/3-540-56939-1_{9}2
Benjamin Steinberg, Möbius functions and semigroup representation theory, J. Combin. Theory Ser. A 113 (2006), no. 5, 866–881. MR 2231092, DOI 10.1016/j.jcta.2005.08.004
B. Steinberg, Möbius functions and semigroup representation theory. II: Character formulas and multiplicities, arXiv:math.CO/0607564, to appear, Advances in Math.
Howard Straubing, A generalization of the Schützenberger product of finite monoids, Theoret. Comput. Sci. 13 (1981), no. 2, 137–150. MR 594057, DOI 10.1016/0304-3975(81)90036-0
Pascal Tesson and Denis Thérien, Diamonds are forever: the variety DA, Semigroups, algorithms, automata and languages (Coimbra, 2001) World Sci. Publ., River Edge, NJ, 2002, pp. 475–499. MR 2023803, DOI 10.1142/9789812776884_{0}021
Denis Thérien, Subword counting and nilpotent groups, Combinatorics on words (Waterloo, Ont., 1982) Academic Press, Toronto, ON, 1983, pp. 297–305 (English, with French summary). MR 910141
Bret R. Tilson, Appendix to “Algebraic theory of finite semigroups”. On the $p$-length of $p$-solvable semigroups: Preliminary results, Semigroups (Proc. Sympos., Wayne State Univ., Detroit, Mich., 1968) Academic Press, New York, 1969, pp. 163–208. MR 0277636
B. Tilson, Depth decomposition theorem, Chapter XI in [S. Eilenberg, “Automata, Languages and Machines”, Academic Press, New York, Vol. A, 1974; Vol. B, 1976].
Bret Tilson, Categories as algebra: an essential ingredient in the theory of monoids, J. Pure Appl. Algebra 48 (1987), no. 1-2, 83–198. MR 915990, DOI 10.1016/0022-4049(87)90108-3
J. H. M. Wedderburn, Note on algebras, Ann. of Math. (2) 38 (1937), no. 4, 854–856. MR 1503377, DOI 10.2307/1968842
Pascal Weil, Closure of varieties of languages under products with counter, J. Comput. System Sci. 45 (1992), no. 3, 316–339. MR 1193376, DOI 10.1016/0022-0000(92)90029-I
Yechezkel Zalcstein, Studies in the representation theory of finite semigroups, Trans. Amer. Math. Soc. 161 (1971), 71–87. MR 283104, DOI 10.1090/S0002-9947-1971-0283104-2