本原字的代数性质和析取性质研究

结题报告

项目介绍

AI项目解读

基本信息

批准号：
11261066
项目类别：
地区科学基金项目
资助金额：
41.0万
负责人：
曹春华
依托单位：
云南大学
学科分类：
A0104.群与代数的结构
结题年份：
2016
批准年份：
2012
项目状态：
已结题
起止时间：
2013-01-01 至2016-12-31

项目参与者：
张静；杨棣；刘祖华；陈丹；刘莉；刘寅；王怡静；杨双；申顺；
关键词：
析取语言强本原字本原字前缀本原字同态映射

项目摘要

In the project, we study the algebraic properties of primitive words and disjunctive languages formed by primitive words and three kinds of special primitive words which is prefix primitive words, strongly primitive words and d-primitive words. The study of algebraic properties and structures of primitive words and disjunctive languages belongs to semigroup theory. First, we will construct two kinds of primitive words. Second, the conditions for homomorphism preserving three kinds of special primitive words will be given. Third, we will propose some disjunctive languages formed by primitive words and special primitive words. Finally, the relationship between left cancellative languages and regular languages with the former disjunctive languages will be discussed. Primitive words play an important role in formal language theory, not only because it is the smallest unit to form a word, that is primitive word cannot be written by powers of any other words, but also primitive words, regular languages and disjunctive languages have important applications in combination mathematics, coding theory, computer science and biology. The project is a basic theortical research on formal language theory, and also provides some primitive words and disjunctive languages which are useful in former fields.

本项目研究本原字和3种特殊本原字：前缀本原字、强本原字和d-本原字的代数性质以及建立由它们的集合和子集形成的析取语言。我们将使用半群代数理论的方法研究形式语言理论中的本原字的代数性质和析取性质。首先，构造2类本原字；然后探讨保持3种特殊本原字的同态映射的充要条件，目的是为了获得多种不同形式的本原字和特殊本原字；接着建立由本原字和3种特殊本原字形成的析取语言；最后探讨左消语言、正则语言与这些析取的关系。本原字在形式语言学中占有极其重要的地位不但是因为它是形成字的最小单元即本原字不能写成任何其它字的方幂，而且本原字、正则语言和析取语言在组合数学、代数编码、计算机科学和生物数学等领域中都有着重要的应用。本项目为这些领域提供多类有用的本原字和析取语言的同时，也是为丰富形式语言学而做的基础理论研究。

结项摘要

本项目研究了本原字和3种特殊本原字：前缀本原字、强本原字和d-本原字的代数性质以及建立由它们的集合和子集形成的析取语言。我们利用半群代数理论的方法研究了形式语言学中的本原字的代数性质和析取性质。首先，构造了多类本原字和非本原字，提供了多种判断字是否是本原字的方法；接着，研究了k-逗号码和k-逗号关联码。逗号自由码是1958年被提出来用于解决DNA中蛋白质的合成问题而提供的一种数学解决方案，1989年证明了逗号自由码中的每一个字都是本原字，逗号码也被用于信息科学中数据压缩的同步延迟中，2011年加拿大学者Bo Cui等提出了k-逗号码和k-逗号关联码，它们分别是逗号自由码和关联码的推广。在本项目的支持下，我们分别用内缀码和双缀码刻画了k-逗号码和k-逗号关联码，探讨了保持k-逗号码和k-逗号关联码的同态映射的充要条件，以及3种特殊本原字的同态映射的条件，目的是为了获得多种不同形式的本原字和特殊本原字；接着建立由本原字和特殊本原字形成的析取语言；最后探讨左消语言、本原字和这些析取的关系。本原字在形式语言学中占有极其重要的地位不但是因为它是形成字的最小单元即本原字不能写成任何其它字的方幂，而且本原字、正则语言和析取语言在组合数学、代数编码、计算机科学和生物数学等领域中都有着重要的应用。本项目为这些领域提供多类有用的本原字和析取语言的同时，也是为丰富形式语言学而做的基础理论研究。