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

批准号:
11401224
项目类别:
青年科学基金项目
资助金额:
22.0 万元
负责人:
陈咏珊
依托单位:
学科分类:
A0104.群与代数的结构
结题年份:
2017
批准年份:
2014
项目状态:
已结题
项目参与者:
泥立丽、张泽锐、吴海彬
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
微信扫码咨询
中文摘要
本项目的研究内容是尝试把Gröbner-Shirshov基理论应用到某些重要的代数系统的复杂度问题上,利用Shirshov算法及既约Gröbner-Shirshov基的性质建立合理的Volume 函数,并通过对Volume函数的研究求出某些重要的群和代数(例如Tompson群,Coxter群等)的Dehn函数和其他复杂度函数,为研究代数系统的复杂性问题提出新的可行的方法。
英文摘要
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基理论应用到某些重要的代数系统的复杂性问题上,求出某些重要的群和代数的Dehn函数和其他复杂性函数。Gröbner基理论在计算机数学,密码学等学科在研究和应用相当成熟,是上个世纪计算代数学中最重大的理论之一, 而Gröbner-Shirshov基理论则是非交换代数中的平行理论,但其应用多局限在代数结构的理论研究中,计算机实现问题一直突破的难点。在计算机科学中,算法复杂度描述了该算法的运行时间,代数系统的复杂性问题主要对象是代数系统各种表示法的时间复杂度和空间复杂度问题, 是代数学如何有效的应用到计算机科学的重要环节因此,本项目的主要工作是研究Shirshov算法的复杂度函数,反映该算法的时间效率。在本项目的研究中,我们通过定义一类新的描述代数结构复杂度的函数Volume函数,利用Gröbner-Shirshov基理论,来研究一些重要的群和代数时间复杂度函数和空间复杂度函数,为研究此类问题提供一种新的可行的方法。 我们给出了群和结合代数的Volume函数的具体定义,找到并证明了Volume函数是复杂度函数的上界的必有条件,并得到了在某些情形下的简单判断方法,也成功地构造并计算了Chinese Monoid,Plactic Monoid以及Coxter群的Volume函数,从而得到了除Plactic Monoid外的上述代数和群的复杂度函数,也给出Plactic Monoid的复杂度函数的上下界。此等成果还没有正式发表。
专著列表
科研奖励列表
会议论文列表
专利列表
国内基金
海外基金
