Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids.

DOI10.1016/j.jalgebra.2014.09.037zbMath1311.20055arXiv1205.4885MaRDI QIDQ479731

António Malheiro, Robert D. Gray, Alan J. Cain

Publication date: 5 December 2014

Published in: Journal of Algebra (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.4885

zbMATH Keywords

Young tableaux; semigroup algebras; Gröbner-Shirshov bases; complete rewriting systems; biautomatic monoids; plactic algebras; plactic monoids

Mathematics Subject Classification ID

16S36: Ordinary and skew polynomial rings and semigroup rings

16S15: Finite generation, finite presentability, normal forms (diamond lemma, term-rewriting)

20M05: Free semigroups, generators and relations, word problems

13P10: Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

20M35: Semigroups in automata theory, linguistics, etc.

68Q42: Grammars and rewriting systems

20M25: Semigroup rings, multiplicative semigroups of rings

Related Items

The monoids of the patience sorting algorithm, Gröbner–Shirshov bases and their calculation, Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids, Quivers of stylic algebras, New approaches to plactic monoid via Gröbner-Shirshov bases., Crystallizing the hypoplactic monoid: from quasi-Kashiwara operators to the Robinson-Schensted-Knuth-type correspondence for quasi-ribbon tableaux, Crystal monoids \& crystal bases: rewriting systems and biautomatic structures for plactic monoids of types \(A_{n}\), \(B_{n}\), \(C_{n}\), \(D_{n}\), and \(G_{2}\), Knuth's coherent presentations of plactic monoids of type A, Tropical plactic algebra, the cloaktic monoid, and semigroup representations, On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids, The stylic monoid, Plactic monoids: a braided approach, Identities of the plactic monoid., Automaticity of one-relator semigroups with length less than or equal to three, Irreducible representations of the plactic algebra of rank four, Plactic key agreement (insecure?), Cohomology rings of the plactic monoid algebra via a Gröbner–Shirshov basis, Tropical representations and identities of plactic monoids, Garside and Quadratic Normalisation: A Survey

Cites Work

• A plactic algebra for semisimple Lie algebras
• Synchronized rational relations of finite and infinite words
• Small cancellation theory and automatic groups
• Polynomial representations of \(GL_n\)
• On crystal bases of the \(q\)-analogue of universal enveloping algebras
• A finiteness condition for rewriting systems
• Noncommutative symmetric functions. IV: Quantum linear groups and Hecke algebras at \(q=0\)
• Notions of automaticity in semigroups.
• Plactic algebras.
• Automatic semigroups
• Crystal graphs and \(q\)-analogues of weight multiplicities for the root system \(A_ n\)
• The Robinson-Schensted correspondence, crystal bases, and the quantum straightening at \(q = 0\)
• Finitely presented algebras and groups defined by permutation relations.
• Finite transducers for divisibility monoids
• Permutations, matrices, and generalized Young tableaux
• Artin groups of large type are shortlex automatic with regular geodesics
• Gröbner-Shirshov Bases for Plactic Algebras
• Singular Artin Monoids of Finite Coxeter Type Are Automatic
• Longest Increasing and Decreasing Subsequences
• GRÖBNER–SHIRSHOV BASIS FOR THE CHINESE MONOID
• On the Homology of Associative Algebras
• String rewriting and homology of monoids
• Automatic monoids and change of generators
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Fundamentals of Computation Theory
• The shifted plactic monoid
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item