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

项目名称： 几类半群在图论和形式语言学中的应用

项目编号： No.11301470

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 王守峰

作者单位： 云南师范大学

项目金额： 22万元

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

中文关键词： 半群；凯莱图；格林图；PS-正则语言；句法半群

英文摘要： 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.

英文关键词： Semigroups；Cayley graphs；Green graphs；PS-regular languages；Syntactic monoids