几类半群在图论和形式语言学中的应用

The theory of semigroups has been investigated systematically for more than 60 years. It is shown that semigroups not only have abundant research contents but also have extensive applications in other subjects and branches, such as algebraic graph theory, formal language theory and information science. The aim of this program is mainly to study some applications of the theory of semigroups in algebraic graph theory and formal language theory. More precisely, the following two items will be considered: (1) Investigate some properties of vertex-transitive Cayley graphs of semigroups concerning the following important problem: Does any vertex-transitive Cayley graph of semigroups be always Cayley (i.e. isomorphic to some Cayley graph of some group), and find an answer of this problem for some special classes of semigroups;(2) Classify PS-regular languages by using their generalized syntactic monoids and describe the generalized syntactic complexities of PS-regular languages. The investigations of the above two items are related closely, and the main tools in these investigations are the algebraic theory of some special semigroups such as groups, finite semigroups and completely simple semigroups.

半群理论已经过60余年的系统研究。实践证明，半群不仅自身有其丰富的研究内容，而且在其他学科分支（诸如代数图论，形式语言学和信息科学等）更是有广泛的应用。本项目主要考虑半群理论在代数图论和形式语言学中的一些应用。具体说来，本项目拟研究如下两个方面的问题：（1） 围绕"点传递半群凯莱图是否均为凯莱的（即同构于某个群的凯莱图）"这一重要问题，研究点传递半群凯莱图的性态，就某些特殊半群回答该问题；（2）利用广义句法幺半群对PS-正则语言进行分类并描述这类语言的广义句法复杂性（generalized syntactic complexity）。上述两项内容的研究密切相关且均以某些特殊半群（例如，群，有限半群，完全单半群）的代数理论为主要工具。

本项目为2013年立项，2014年开始执行的为期3年的青年科学基金项目。项目的立项背景是研究半群代数理论，图论及形式语言理论等3个数学分支的交叉作用。本项目执行期内进行的主要研究内容有：几类半群的结构理论和同余理论；几类半群的凯莱图和格林图的代数性质和组合性质；与同步码及完全单码相关的句法半群的代数结构；半群的Burnside问题及其在形式语言理论中的应用。. 本项目获得了强P-正则半群，具有quasi-Ehresmann断面的半富足半群，具有正则*-断面的正则半群以及具有ample断面的富足半群等半群类的精细的代数结构，这是研究这些半群上的凯莱图和格林图的必备基础；给出了半群凯莱图同构于群凯莱图的若干充分或必要条件，证明了每个有限的，连通的点传递的无向半群凯莱图均同构于某群的凯莱图，据此证明了著名的Petersen图不同构于任何半群的凯莱图；得到了纯正的完全0-单半群（一种特殊的强P-正则半群）上某些凯莱图同构的充分必要条件；获得了半群格林图的若干性质，证明了任何有限无向图均同构于某个半群的左格林图；得到了与一类同步码有关的句法半群的代数结构，并将相应结果推广至更广泛的完全单码；研究了半群的Burnside问题，得到了有限生成半群是有限半群的一个新的充要条件并借此解决了上世纪80年代提出的一个关于形式语言理论的问题。项目目前共完成学术论文13篇，其中已发表8篇（SCI收录5篇，CSCD收录2篇），录用待发表2篇（SCI源刊1篇），已投稿1篇（SCI源刊），即将投稿2篇。. 本项目在半群的代数结构，半群的凯莱图与格林图，与PS-正则语言相关的句法半群等方面均取得了一些有意义的结果。第一部分结果揭示了几类半群的代数结构，这些结果不仅是研究这些半群上的凯莱图和格林图的必备基础，同时也对深刻理解这些半群类有重要意义。第二部分结果就某些重要的特殊情形回答了“是否每个点传递半群凯莱图均同构于某群的凯莱图”这一在半群凯莱图理论中具有基本重要性的问题；用半群的格林图重新构建了任意有限无向图。这些结果对认识点传递半群凯莱图及掌握半群的格林图的性质及应用都有重要价值。第三部分结果涉及到的是半群在形式语言理论中的应用，所得结果从代数角度反映了相关语言的特有性质，为研究这些语言提供了新的思路和途径。