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

DOI10.1016/J.JALGEBRA.2014.09.037zbMATH Open1311.20055arXiv1205.4885OpenAlexW2054644771MaRDI QIDQ479731FDOQ479731

Authors: Alan J. Cain, R. Gray, A. Malheiro 

Publication date: 5 December 2014

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

Abstract: This paper shows that every Plactic algebra of finite rank admits a finite Gr"obner--Shirshov basis. The result is proved by using the combinatorial properties of Young tableaux to construct a finite complete rewriting system for the corresponding Plactic monoid, which also yields the corollaries that Plactic monoids of finite rank have finite derivation type and satisfy the homological finiteness properties left and right $F{P}_{i}nfty$. Also, answering a question of Zelmanov, we apply this rewriting system and other techniques to show that Plactic monoids of finite rank are biautomatic.

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

Recommendations

• New approaches to plactic monoid via Gröbner-Shirshov bases.
• Gröbner-Shirshov bases for plactic algebras.
• Cohomology rings of the plactic monoid algebra via a Gröbner-Shirshov basis
• Gröbner-Shirshov bases for free idempotent monoids
• Gröbner-Shirshov bases of some monoids.
• A Gröbner-Shirshov basis over a special type of braid monoids
• Gröbner-Shirshov bases for \(S\)-act algebras.
• Gröbner-Shirshov bases for commutative dialgebras
• Gröbner-Shirshov bases for dialgebras
• Gröbner-Shirshov bases for Rota-Baxter algebras.

zbMATH Keywords

semigroup algebrasYoung tableauxcomplete rewriting systemsbiautomatic monoidsplactic algebrasplactic monoidsGröbner-Shirshov bases

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (27)

• The stylic monoid
• Irreducible representations of the plactic algebra of rank four
• Finite convergent presentation of plactic monoid for type C.
• The monoids of the patience sorting algorithm
• From plactic monoids to hypoplactic monoids
• Tropical representations and identities of plactic monoids
• Rewriting systems and biautomatic structures for Chinese, hypoplactic, and Sylvester monoids.
• Gröbner-Shirshov bases and their calculation
• Automaticity of one-relator semigroups with length less than or equal to three
• Coherence for plactic monoids via rewriting theory and crystal structures
• Garside and quadratic normalisation: a survey
• Knuth's coherent presentations of plactic monoids of type A
• The shifted plactic monoid (extended abstract)
• Confluence of the Chinese Monoid
• Plactic monoids: a braided approach
• On the first order theory of plactic monoids
• Identities of the plactic monoid.
• Plactic key agreement (insecure?)
• Cohomology rings of the plactic monoid algebra via a Gröbner-Shirshov basis
• Gröbner-Shirshov bases for plactic algebras.
• New approaches to plactic monoid via Gröbner-Shirshov bases.
• 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}\)
• Tropical plactic algebra, the cloaktic monoid, and semigroup representations
• The lexicographic cross-section of the plactic monoid is regular
• Crystallizing the hypoplactic monoid: from quasi-Kashiwara operators to the Robinson-Schensted-Knuth-type correspondence for quasi-ribbon tableaux
• Quivers of stylic algebras
• On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids

This page was built for publication: Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q479731)