Projects per year
Abstract
The vertices of any (combinatorial) Kashiwara crystal graph carry a natural monoid structure given by identifying words labelling vertices that appear in the same position of isomorphic components of the crystal. Working on a purely combinatorial and monoidtheoretical level, we prove some foundational results for these crystal monoids, including the observation that they have decidable word problem when their weight monoid is a finite rank free abelian group. The problem of constructing finite complete rewriting systems, and biautomatic structures, for crystal monoids is then investigated. In the case of Kashiwara crystals of types A_{n}, B_{n}, C_{n}, D_{n}, and G_{2} (corresponding to the qanalogues of the Lie algebras of these types) these monoids are precisely the generalised plactic monoids investigated in work of Lecouvey. We construct presentations via finite complete rewriting systems for all of these types using a unified proof strategy that depends on Kashiwara's crystal bases and analogies of Young tableaux, and on Lecouvey's presentations for these monoids. As corollaries, we deduce that plactic monoids of these types have finite derivation type and satisfy the homological finiteness properties left and right FP_{∞}. These rewriting systems are then applied to show that plactic monoids of these types are biautomatic and thus have word problem soluble in quadratic time.
Original language  English 

Pages (fromto)  406466 
Number of pages  61 
Journal  Journal of Combinatorial Theory, Series A 
Volume  162 
Early online date  15 Nov 2018 
DOIs  
Publication status  Published  Feb 2019 
Keywords
 Automatic monoid
 Crystal basis
 Plactic monoid
 Rewriting system
 Tableaux
Profiles

Robert Gray
 School of Mathematics  Reader in Pure Mathematics
 Algebra and Combinatorics  Member
 Logic  Member
Person: Research Group Member, Academic, Teaching & Research
Projects
 1 Finished