句法幺半群在形式语言学和码论中的若干应用

对形式语言和码的研究是计算机科学中的重要内容. 由于形式语言学和码论不仅与理论计算机科学、代数学、组合学、概率论等一些理论性学科的发展密切相关, 而且在许多新兴的应用性学科如运筹学、控制论、最优化理论、密码学、生物信息学中都有重要的应用, 因此其发展越来越受到人们的关注. 研究语言和码最常用的工具是自动机与文法. 它们都是表示语言和码很有效的组合工具. 为了研究语言和码的层次结构, 从上世纪五十年中期开始, 就有许多学者开始研究如何利用代数工具刻画语言和码. 半群就是一种很有效的研究语言和码的代数工具. 本项目拟利用句法幺半群与传统组合工具相结合的方法去研究语言和码. 主要对一般半群的句法性、广义析取语言的层次结构和分类、相对正则语言的刻画与分类、各种码类生成的星号语言以及极大码的组合性质等内容进行研究. 这些问题都是紧密联系在一起的, 并且都能有效的利用句法幺半群这一代数工具.

形式语言和码一直是计算机科学中最基本的研究对象. 其理论不仅在计算机科学、数学的许多领域中有重要意义, 而且在信息化程度越来越高的现代社会中也有着广泛的应用. 研究形式语言和码的工具有很多. 除了最常见的自动机和文法以外, 句法幺半群也是一种重要的工具. 本项目主要利用这种工具对某些形式语言和码的代数与组合性质、层次结构与分类等问题进行研究. 得到的主要结果如下: .(1) 证明了稀疏极大前缀码的群分解定理去掉前缀条件后将不再成立. 这是码论中三十年前提出的一个公开问题..(2) 给出了矩形群码的分解定理..(3) 对完全单码进行了系统研究, 给出了这种码的层次结构与分类刻画. .(4) 对由前缀码、后缀码、双缀码、内缀码、外缀码等码类决定的广义析取语言类的组合与代数性质进行了研究. 并利用泛代数给出了这些语言类的一般理论. 另外, 我们还得到了常见广义析取语言类的层次关系图..(5) 对3次极大双缀码进行了研究. 解决了有限3次极大双缀码的构造与分类问题..(6) 对半群中的稠密子集与析取子集的基本代数性质、保持稠密子集的同态、稠密元的性质等进行了刻画..(7) 对稠密极大双缀码进行了研究, 发现稀疏极大双缀码的八个等价刻画在去掉稀疏性条件后将互不等价, 并给出了相应的八个码类的相互关系. .(8) 给出了0-群码的结构刻画..(9) 对一些类型的子幺半群定义的码类和语言类进行了研究, 刻画了它们的性质及相互关系.