Crystal monoids crystal bases: Rewriting systems and biautomatic structures for plactic monoids of types A, B, C, D, and G2

摘要

The vertices of any (combinatorial) Kashiwara crystal graph carry a naturalmonoid structure given by identifying words labelling vertices that appear inthe same position of isomorphic components of the crystal. We prove somefoundational results for these crystal monoids, including the observation thatthey have decidable word problem when their weight monoid is a finite rank freeabelian group. The problem of constructing finite complete rewriting systems,and biautomatic structures, for crystal monoids is then investigated. In thecase of Kashiwara crystals of types $A_n$, $B_n$, $C_n$, $D_n$, and $G_2$(corresponding to the $q$-analogues of the Lie algebras of these types) thesemonoids are precisely the generalised plactic monoids investigated in work ofLecouvey. We construct presentations via finite complete rewriting systems forall of these types using a unified proof strategy that depends on Kashiwara'scrystal bases and analogies of Young tableaux, and on Lecouvey's presentationsfor these monoids. As corollaries, we deduce that plactic monoids of thesetypes have finite derivation type and satisfy the homological finitenessproperties left and right $mathrm{FP}_infty$. These rewriting systems arethen applied to show that plactic monoids of these types are biautomatic andthus have word problem soluble in quadratic time.