Gröbner-Shirshov基与代数系统复杂度问题的一些研究

The main goal of this project is to apply the Gröbner-Shirshov bases theory to the complexity problem of some important algebraic systems. By using the Shirshov's algorithm and the property of reduced Gröbner-Shirshov bases, we are trying to construct so called Volume functions which are upper bounds of many other complexity functions, and are trying to find the Dehn functions, growth functions and other related complexity functions of some important groups and algebras(for example, Tompson groups, Coxter groups and so on). It is a new method to study the complexity problem of algebraic systems.

本项目的研究内容是尝试把Gröbner-Shirshov基理论应用到某些重要的代数系统的复杂度问题上，利用Shirshov算法及既约Gröbner-Shirshov基的性质建立合理的Volume 函数，并通过对Volume函数的研究求出某些重要的群和代数（例如Tompson群，Coxter群等）的Dehn函数和其他复杂度函数，为研究代数系统的复杂性问题提出新的可行的方法。

本项目的研究内容是把Gröbner-Shirshov基理论应用到某些重要的代数系统的复杂性问题上，求出某些重要的群和代数的Dehn函数和其他复杂性函数。Gröbner基理论在计算机数学，密码学等学科在研究和应用相当成熟，是上个世纪计算代数学中最重大的理论之一, 而Gröbner-Shirshov基理论则是非交换代数中的平行理论，但其应用多局限在代数结构的理论研究中，计算机实现问题一直突破的难点。在计算机科学中，算法复杂度描述了该算法的运行时间，代数系统的复杂性问题主要对象是代数系统各种表示法的时间复杂度和空间复杂度问题, 是代数学如何有效的应用到计算机科学的重要环节因此，本项目的主要工作是研究Shirshov算法的复杂度函数，反映该算法的时间效率。在本项目的研究中，我们通过定义一类新的描述代数结构复杂度的函数Volume函数，利用Gröbner-Shirshov基理论，来研究一些重要的群和代数时间复杂度函数和空间复杂度函数，为研究此类问题提供一种新的可行的方法。 我们给出了群和结合代数的Volume函数的具体定义，找到并证明了Volume函数是复杂度函数的上界的必有条件，并得到了在某些情形下的简单判断方法，也成功地构造并计算了Chinese Monoid，Plactic Monoid以及Coxter群的Volume函数，从而得到了除Plactic Monoid外的上述代数和群的复杂度函数，也给出Plactic Monoid的复杂度函数的上下界。此等成果还没有正式发表。