×

Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids. (English) Zbl 1311.20055

The plactic monoid \(M_n\) with finite generating set \(A=\{1,2,\ldots,n\}\) is considered. Recall that the elements of \(M_n\) are in a one-to-one correspondence with semistandard Young tableaux, see A. Lascoux, B. Leclerc and J.-Y. Thibon [Algebraic combinatorics on words. Cambridge: Cambridge Univ. Press (2002; Zbl 1001.68093)]. A presentation of \(M_n\) based on the set of generators consisting of all columns (defined as the decreasing words) and with the set of defining relations, each involving a word of length \(2\) and a word of length at most \(2\) in these generators, is given. A finite complete rewriting system is derived, which leads to a finite Gröbner-Shirshov basis for the corresponding semigroup algebra, with respect to the degree-lexicographic order. The latter construction was independently obtained by L. A. Bokut et al. [J. Algebra 423, 301-317 (2015; Zbl 1309.16014)]. It follows that plactic monoids of finite rank have finite derivation type and satisfy the homological finiteness properties left and right \(FP_\infty\). The constructed rewriting system is also applied to show that plactic monoids of finite rank are biautomatic, with respect to the usual generating set \(A\).

MSC:

20M05 Free semigroups, generators and relations, word problems
20M25 Semigroup rings, multiplicative semigroups of rings
20M35 Semigroups in automata theory, linguistics, etc.
68Q42 Grammars and rewriting systems
16S15 Finite generation, finite presentability, normal forms (diamond lemma, term-rewriting)
16S36 Ordinary and skew polynomial rings and semigroup rings
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
05E15 Combinatorial aspects of groups and algebras (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Schensted, C., Longest increasing and decreasing subsequences, Canad. J. Math., 13, 179-191 (1961) · Zbl 0097.25202
[2] Knuth, D. E., Permutations, matrices, and generalized Young tableaux, Pacific J. Math., 34, 709-727 (1970) · Zbl 0199.31901
[3] Lascoux, A.; Schützenberger, M. P., Le monoïde plaxique, (Noncommutative Structures in Algebra and Geometric Combinatorics. Noncommutative Structures in Algebra and Geometric Combinatorics, Naples, 1978. Noncommutative Structures in Algebra and Geometric Combinatorics. Noncommutative Structures in Algebra and Geometric Combinatorics, Naples, 1978, Quad. Ricerca Sci., vol. 109 (1981), CNR: CNR Rome), 129-156
[4] Fulton, W., Young Tableaux, London Math. Soc. Stud. Texts, vol. 35 (1997), Cambridge University Press: Cambridge University Press Cambridge, with applications to representation theory and geometry · Zbl 0878.14034
[5] Lothaire, M., Algebraic Combinatorics on Words, Encyclopedia Math. Appl., vol. 90 (2002), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1001.68093
[6] Green, J. A., Polynomial Representations of \(GL_n\), Lecture Notes in Math., vol. 830 (2007), Springer: Springer Berlin, with an appendix on Schensted correspondence and Littelmann paths by K. Erdmann, Green and M. Schocker · Zbl 0451.20037
[7] Littlewood, D.; Richardson, A., Group characters and algebra, Philos. Trans. R. Soc. Lond. Ser. A, 233, 99-141 (1934) · JFM 60.0896.01
[8] Lascoux, A.; Schützenberger, M. P., Sur une conjecture de H.O. Foulkes, C. R. Acad. Sci. Paris Sér. A-B, 286, 7, A323-A324 (1978)
[9] Date, E.; Jimbo, M.; Miwa, T., Representations of \(U_q(gl(n, C))\) at \(q = 0\) and the Robinson-Shensted [Schensted] correspondence, (Physics and Mathematics of Strings (1990), World Sci. Publ.: World Sci. Publ. Teaneck, NJ), 185-211 · Zbl 0743.17018
[10] Kashiwara, M., On crystal bases of the \(Q\)-analogue of universal enveloping algebras, Duke Math. J., 63, 2, 465-516 (1991) · Zbl 0739.17005
[11] Littelmann, P., A plactic algebra for semisimple Lie algebras, Adv. Math., 124, 2, 312-331 (1996) · Zbl 0892.17009
[12] Lascoux, A.; Leclerc, B.; Thibon, J. Y., Crystal graphs and \(q\)-analogues of weight multiplicities for the root system \(A_n\), Lett. Math. Phys., 35, 4, 359-374 (1995) · Zbl 0854.17014
[13] Krob, D.; Thibon, J. Y., Noncommutative symmetric functions. IV. Quantum linear groups and Hecke algebras at \(q = 0\), J. Algebraic Combin., 6, 4, 339-376 (1997) · Zbl 0881.05120
[14] Leclerc, B.; Thibon, J. Y., The Robinson-Schensted correspondence, crystal bases, and the quantum straightening at \(q = 0\), Electron. J. Combin., 3, 2 (1996), Research Paper 11, approx. 24 pp. (electronic), the Foata Festschrift · Zbl 0852.05079
[15] Serrano, L., The shifted plactic monoid, Math. Z., 266, 2, 363-392 (2010) · Zbl 1231.05279
[16] Duchamp, G.; Krob, D., Plactic-growth-like monoids, (Words, Languages and Combinatorics, II. Words, Languages and Combinatorics, II, Kyoto, 1992 (1994), World Sci. Publ.: World Sci. Publ. River Edge, NJ), 124-142 · Zbl 0875.68720
[17] Schützenberger, M. P., Pour le monoïde plaxique, Math. Inform. Sci. Hum., 140, 5-10 (1997) · Zbl 0948.20040
[18] Cedó, F.; Okniński, J., Plactic algebras, J. Algebra, 274, 1, 97-117 (2004) · Zbl 1054.16022
[19] Lascoux, A.; Schützenberger, M. P., Keys & standard bases, (Invariant Theory and Tableaux. Invariant Theory and Tableaux, Minneapolis, MN, 1988. Invariant Theory and Tableaux. Invariant Theory and Tableaux, Minneapolis, MN, 1988, IMA Vol. Math. Appl., vol. 19 (1990), Springer: Springer New York), 125-144 · Zbl 0815.20013
[20] Cedó, F.; Jespers, E.; Okniński, J., Finitely presented algebras and groups defined by permutation relations, J. Pure Appl. Algebra, 214, 7, 1095-1102 (2010) · Zbl 1196.16022
[21] Kubat, Ł.; Okniński, J., Gröbner-Shirshov bases for plactic algebras, Algebra Colloq., 21, 4, 591 (2014) · Zbl 1304.16026
[22] Güzel Karpuz, E., Complete rewriting system for the Chinese monoid, Appl. Math. Sci. (Ruse), 4, 21-24, 1081-1087 (2010) · Zbl 1198.20045
[23] Chen, Y.; Qiu, J., Gröbner-Shirshov basis for the Chinese monoid, J. Algebra Appl., 7, 5, 623-628 (2008) · Zbl 1165.16013
[24] Heyworth, A., Rewriting as a special case of non-commutative Gröbner basis theory, (Computational and Geometric Aspects of Modern Algebra. Computational and Geometric Aspects of Modern Algebra, Edinburgh, 1998. Computational and Geometric Aspects of Modern Algebra. Computational and Geometric Aspects of Modern Algebra, Edinburgh, 1998, London Math. Soc. Lecture Note Ser., vol. 275 (2000), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 101-105 · Zbl 0996.16034
[25] Chen, Y.; Li, J., New approach to Schensted-Knuth normal forms
[26] Epstein, D. B.A.; Cannon, J. W.; Holt, D. F.; Levy, S. V.F.; Paterson, M. S.; Thurston, W. P., Word Processing in Groups (1992), Jones & Bartlett: Jones & Bartlett Boston, MA · Zbl 0764.20017
[27] Campbell, C. M.; Robertson, E. F.; Ruškuc, N.; Thomas, R. M., Automatic semigroups, Theoret. Comput. Sci., 250, 1-2, 365-391 (2001) · Zbl 0987.20033
[28] Gersten, S. M.; Short, H. B., Small cancellation theory and automatic groups, Invent. Math., 102, 2, 305-334 (1990) · Zbl 0714.20016
[29] Holt, D. F.; Rees, S., Artin groups of large type are shortlex automatic with regular geodesics, Proc. Lond. Math. Soc. (3), 104, 3, 486-512 (2012) · Zbl 1275.20034
[30] Gromov, M., Hyperbolic groups, (Gersten, S. M., Essays in Group Theory. Essays in Group Theory, Math. Sci. Res. Inst. Publ., vol. 8 (1987), Springer: Springer New York), 75-263 · Zbl 0634.20015
[31] Picantin, M., Finite transducers for divisibility monoids, Theoret. Comput. Sci., 362, 1-3, 207-221 (2006) · Zbl 1100.68057
[32] Corran, R.; Hoffmann, M.; Kuske, D.; Thomas, R. M., Singular Artin monoids of finite Coxeter type are automatic, (Language and Automata Theory and Applications. Language and Automata Theory and Applications, Lecture Notes in Comput. Sci., vol. 6638 (2011)), 250-261 · Zbl 1295.20062
[33] Lohrey, M., Decidability and complexity in automatic monoids, Internat. J. Found. Comput. Sci., 16, 4, 707-722 (2005) · Zbl 1146.20314
[34] Otto, F., On Dehn functions of finitely presented bi-automatic monoids, J. Autom. Lang. Comb., 5, 4, 405-419 (2000) · Zbl 0964.68075
[35] Otto, F.; Sattler-Klein, A.; Madlener, K., Automatic monoids versus monoids with finite convergent presentations, (Rewriting Techniques and Applications. Rewriting Techniques and Applications, Tsukuba, 1998. Rewriting Techniques and Applications. Rewriting Techniques and Applications, Tsukuba, 1998, Lecture Notes in Comput. Sci., vol. 1379 (1998), Springer: Springer Berlin), 32-46 · Zbl 0914.20052
[36] Book, R. V.; Otto, F., String-Rewriting Systems, Texts Monogr. Comput. Sci (1993), Springer-Verlag: Springer-Verlag New York · Zbl 0832.68061
[37] Ufnarovski, V., Introduction to noncommutative Gröbner bases theory, (Gröbner Bases and Applications. Gröbner Bases and Applications, Linz, 1998. Gröbner Bases and Applications. Gröbner Bases and Applications, Linz, 1998, London Math. Soc. Lecture Note Ser., vol. 251 (1998), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 259-280 · Zbl 0902.16002
[38] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley Publishing Co.: Addison-Wesley Publishing Co. Reading, MA · Zbl 0426.68001
[39] Berstel, J., Transductions and Context-Free Languages, Leitfäden der Angewandten Mathematik und Mechanik, vol. 38 (1979), B.G. Teubner: B.G. Teubner Stuttgart · Zbl 0424.68040
[40] Duncan, A. J.; Robertson, E. F.; Ruškuc, N., Automatic monoids and change of generators, Math. Proc. Cambridge Philos. Soc., 127, 3, 403-409 (1999) · Zbl 0941.20065
[41] Hoffmann, M.; Thomas, R. M., Biautomatic semigroups, (Fundamentals of Computation Theory. Fundamentals of Computation Theory, Lecture Notes in Comput. Sci., vol. 3623 (2005), Springer: Springer Berlin), 56-67 · Zbl 1123.68073
[42] Frougny, C.; Sakarovitch, J., Synchronized rational relations of finite and infinite words, International Colloquium on Words, Languages and Combinatorics. International Colloquium on Words, Languages and Combinatorics, Kyoto, 1990. International Colloquium on Words, Languages and Combinatorics. International Colloquium on Words, Languages and Combinatorics, Kyoto, 1990, Theoret. Comput. Sci., 108, 1, 45-82 (1993) · Zbl 0783.68065
[43] Squier, C. C.; Otto, F.; Kobayashi, Y., A finiteness condition for rewriting systems, Theoret. Comput. Sci., 131, 2, 271-294 (1994) · Zbl 0863.68082
[44] Anick, D. J., On the homology of associative algebras, Trans. Amer. Math. Soc., 296, 2, 641-659 (1986) · Zbl 0598.16028
[45] Cohen, D. E., String rewriting and homology of monoids, Math. Structures Comput. Sci., 7, 3, 207-240 (1997) · Zbl 0878.18003
[46] Hoffmann, M.; Thomas, R. M., Notions of automaticity in semigroups, Semigroup Forum, 66, 3, 337-367 (2003) · Zbl 1035.20045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.