强双奇异语言和极大左消语言与本原字和非本原字的代数性质研究

In the project, we want to know whether the union of all indecomposable strongly bi-singular languages and the language of all primitive words is a code or not, and whether the union of all indecomposable strongly bi-singular languages and the language of all i-power primitive words is a code or not. So we can solve that the monoid which is generated by strongly bi-singular languages or maximal left cancellative languages and the language of all primitive words or i-power primitive words is free or not. As well known, the monoid of prefix codes is free, but the monoid of left singular languages, which is a kind of generation of prefix code, is not free. Meanwhile, the monoid of strongly bi-singular languages, which is between the monoid of prefix codes and the monoid of left singular languages, is free. In 1998, some mathematicans proved that the monoid which is generated by all finite prefix codes and the language of all primitive words is free. In our project, we will prove that the monoid which is generated by strongly bi-singular languages or maximal left cancellative languages and the language of all primitive words or i-power primitive words are free or not free. It is a small human progress in finding a free monoid larger than the free monoid of prefix codes. Prefix codes and primitive words play an important role in formal language theory, not only because they are the basic objects in formal language theory, but also because they have important applications in computer science, combination mathematics, coding theory and biology. The project, which is a basic theortical research on algebra, provides some codes which are useful in former fields.

本项目研究不可分解的强双奇异语言分别与本原字的集合构成的语言和本原字的 i 次方幂的集合构成的语言是否是码。从而，解决强双奇异语言与本原字语言、本原字的 i 次方幂语言生成的幺半群是否是自由幺半群；进一步，解决极大左消语言与它们生成的幺半群的自由性问题。众所周知，前缀码的集合是自由幺半群，作为其代数性质推广的左奇异语言和左消语言的集合不是自由幺半群，而处于前缀码和左奇异语言之间的强双奇异语言的集合是自由幺半群；以及，有限前缀码与本原字语言生成的幺半群也是自由的。我们致力于探讨强双奇异语言和极大左消语言与本原字语言和本原字的 i 次方幂语言生成的幺半群的自由性问题。以期找到比前缀码自由幺半群更大的自由幺半群。前缀码和本原字是形式语言学中最基本的研究对象，重要的是，它们在信息科学、组合数学、代数编码和生物学等领域有着广泛应用。本项目可为这些领域提供一些有用途的代数码，同时也丰富了半群代数理论。

前缀码和本原字在计算机科学中的数据储存和压缩、编码和译码等中有着重要应用。本项目从最基础的信息码特性的角度，利用半群代数理论中研究码的句法幺半群的特色、方法和手段，研究了代数码论中的前缀码、强双奇异语言、固码、本原字和本原字的方幂，证明了所有不可分解的强双奇异语言与本原字语言的并集不是码，但是，当i≥2时，所有不可分解的强双奇异语言本原字的i次方幂作成的语言的并集是码，于是强双奇异语言与本原字的i次方幂语言生成的幺半群是自由幺半群；证明了一个自由幺半群上的固码的句法同余与一般半群代数理论中的Reis同余的一些特殊同余之间的等价关系，对固码的句法幺半群进行了详细刻画，得到了固码的句法同余与在研究一般半群时定义的Reis同余是等价的，从而推进我们以后可以将研究半群的方法、手段和结果应用在固码或者代数码论中其它代数码的代数性质的研究中；探讨了码在计算机信息处理中的应用技术。本项目以理论研究为主，其成果的表现形式是发表论文。经过4年的研究工作，我们在国际SCI刊物发表科学研究论文3篇，被国内SCI刊物《高校数学应用学报（B辑）》接收论文1篇；在高水平学术刊物上发表论文6篇，其中科学研究论文5篇，教学研究论文1篇。通过该项目的实施，项目负责人培养硕士研究生9名，项目组成员培养硕士研究生3名；并与本研究方向相近的境内外专家进行了积极交流，建立了稳定的合作关系，为以后的研究工作奠定了良好的基础。