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

DOI10.1016/J.JALGEBRA.2014.09.037MaRDI QIDQ479731zbMATH OpenOpenAlexFDO

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

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

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)

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.

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.

Cites work

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

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
• Tropical representations and identities of plactic monoids
• From plactic monoids to hypoplactic 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)
• Plactic monoids: a braided approach
• Confluence of the Chinese Monoid
• On the first order theory of plactic monoids
• Identities of the plactic monoid.
• Plactic key agreement (insecure?)
• New approaches to plactic monoid via Gröbner-Shirshov bases.
• Cohomology rings of the plactic monoid algebra via a Gröbner-Shirshov basis
• Gröbner-Shirshov bases for plactic algebras.
• 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)