Crystal monoids & crystal bases: Rewriting systems and biautomatic structures for plactic monoids of types A, B, C, D, and G2
Crystal monoids & crystal bases: Rewriting systems and biautomatic structures for plactic monoids of types A, B, C, D, and G2
复制标题
晶体幺半群
DOI：
10.1016/j.jcta.2018.11.010
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Cain A
中科院分区：
文献类型：
--
作者：
Cain A
任何（组合）柏原晶体图的顶点都带有一个自然的幺半群结构，该结构通过识别出现在晶体的同构分量的相同位置的标记顶点的单词来给出。工作在一个纯粹的组合和幺半群理论水平，我们证明了这些晶体幺半群的一些基本结果，包括观察，他们有判定字的问题时，他们的重量幺半群是一个有限秩自由阿贝尔群。构造有限的完全重写系统，和双自动结构，晶体幺半群的问题，然后进行了研究。在柏原晶体的情况下，类型A n，B n，C n，D n，和G 2（对应于q-类似物的李代数这些类型）这些幺半群正是广义plastic幺半群的研究工作Lecouvey。我们构建演示文稿通过有限的完全重写系统，所有这些类型使用统一的证明策略，取决于柏原的晶体基地和类比的年轻tableaux，并在Lecouvey的介绍这些monoids。作为推论，我们证明了这类platic么半群具有有限导子型，并满足左、右同调有限性FP∞.这些重写系统，然后施加到这些类型的plastic幺半群是双自动的，从而有字的问题，解决在二次时间。
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 monoid-theoretical 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 q-analogues 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.