改写系统的Word问题的算法及其复杂性

讨论一类特殊集———有限群上的Word问题的可判断性及其算法。给出图厄系统及改写系统的定义,并证明了在有限改写系统上的Word问题是可判断的并给出了具有线性运行时间的算法。     

一类有限交换环上的广义单位Cayley图的若干性质

设R是一个含有非零单位元的有限交换环,U(R)是R的单位群,G是U(R)的一个乘法子群,S是G的一个非空子集并且S-1={s-1|s∈S}S。单位Cayley图Cay(R,U(R))的顶点集是R,两个顶点x和y相邻当且仅当x-y∈U(R);而广义单位Cayley图Γ(R,G,S)的顶点集为R,两个顶点x与y相邻当且仅当存在s∈S,使得x+sy∈G。容易看出,当G=U(R)时,Γ(R,G,{-1})即为单位Cayley图。本文主要利用有限交换环的结构以及群与图的理论,研究了有限交换环上的广义单位Cayley图的一些性质,讨论了Γ(R,G,{s})的正则性,以及Γ(R,U(R),{s})中任意两点的公共邻接点个数和边着色数。     

一类有限交换环上的广义单位Cayley图的若干性质

设R是一个含有非零单位元的有限交换环,U(R)是R的单位群,G是U(R)的一个乘法子群,S是G的一个非空子集并且S-1={s-1|s∈S}S。单位Cayley图Cay(R,U(R))的顶点集是R,两个顶点x和y相邻当且仅当x-y∈U(R);而广义单位Cayley图Γ(R,G,S)的顶点集为R,两个顶点x与y相邻当且仅当存在s∈S,使得x+sy∈G。容易看出,当G=U(R)时,Γ(R,G,{-1})即为单位Cayley图。本文主要利用有限交换环的结构以及群与图的理论,研究了有限交换环上的广义单位Cayley图的一些性质,讨论了Γ(R,G,{s})的正则性,以及Γ(R,U(R),{s})中任意两点的公共邻接点个数和边着色数。     

恰有2个中心且带刺的完全图对应的有限交换环

设R是带有1的交换环,环R的零因子图Γ(R)是一个简单图,其中图的顶点是R的所有非零的零因子,且顶点x与顶点y有边当且仅当x≠y,且xy=0.文章主要刻画了一类有限交换局部环,使得它们的零因子图是恰有2个中心且带刺的完全图.     

有限交换环上的Chowla定理

设R={r_0,r_1,…,r_(n-1)}是一个有限含幺交换环,若对于r_0,r_1,…,r_(n-1)的任意排列s_0,s_1,…,s_(n-1)都有{r_is_i|0≤i≤n-1}≠R,则称R为M-环.讨论了M-环的基本性质,利用有限交换环的结构定理,得到了R为M-环的判定条件.这些结论将整数环上关于剩余系的Chowla定理推广到M-环上,进而统一证明了Chowla定理以及孙琦和旷京华给出的代数整数环上的Chowla定理.此外还给出有限交换环上置换多项式一个结论的简单证明.     

一些有限群的非交换图

一个群的非交换图以这个群的非中心元素作为顶点,当其中某两点不交换时这两点相连.该文讨论了一些有限非交换群的非交换图的性质,并且详细刻画了14阶以内的非交换群的非交换图以及它们的基本性质.     

有限交换环上Ramanujan单位一-匹配双凯莱图

设R是有单位元1≠0的有限交换环,R上的单位一-匹配双凯莱图记为G_R=BC(R; R^×, R^×, {0}),其中R^×表示R单位的集合。若一个k-正则图G的任意具有|λ|≠k的特征值λ满足|λ|≤2(k-1)^1/2,则称这个k-正则图是Ramanujan图。给出R上的单位一-匹配双凯莱图G_R及其线图是Ramanujan图的充要条件。     

哈密尔顿单位凯莱图

设R是有单位元1的交换环,且1≠0.环R的单位凯莱图,记作Γ(R),是一个简单图,图的顶点是环R的所有元素,且两个互异顶点x与y相邻当且仅当x-y是R的单位即可逆元.该文证明了若有限环交换R不同构于模2的剩余类环Z_2,则环R的单位凯莱图Γ(R)是哈密尔顿图当且仅当Γ(R)是连通图.     

有限群上几个问题的算法及复杂度分析

本文讨论有限群上几个计算问题。我们设了一个O(n~2)时间的算法去查找n阶Abel群的基底(把n阶Abel群分解为循环P群的直积)。给出了复杂度为O(n~2log_2n)的n阶Abel群的检验算法。证明了n阶Abel群的同构检验可在O(nlOg_2n)时间内完成。最后,我们讨论定义在有限群上的旅行售货员问题:证明了该问题是NP完全的,并给出了一个O(m·n~2·2~n)时间的算法求解它。     

有限可交换Thue系统

串重写系统（∑：R）是定义在字母表∑上的所有字符串的集合,一般情况下集合中的元素是不可刻画的。对于一个有限可交换的Thue系统（∑：R）令△R={((t1,t2,……,tn),(s1,s2,……,sn））│(a^t11a^t22……a^tnn→a^s1a^s22……a^snn)∈R}。△R是幺群N^n的一个二元关系,用△*R表示N^n上由△生成的同余,则有（∑：R）≌N^n/△*R。反之,关于N^n的任意同余θ,令∑={a1,a2,……,an}和R1={a^t11a^t22……a^tnn→a^s11a^s22……a^snn│((t1,t2,……,tn),(s1,s2,……,sn))∈θ}。记R=R1U{aiaj→ajai│i≠j,i,j=1,……,n}。则（∑：R）是有限交换的串重写系统,并且（∑：R）≌N^n/θ。     

特殊可交换Thue系统的完备化

给出了判定可交换特殊 Thue系统完备化的方法 .对于所考虑的 Thue系统 ,检验 Church-Rosser性质可进行系统完备化判定 .而使 Church- Rosser性质成立的重叠条件在规则的向量形式表示下 ,可归结为规则的分量满足若干性质 ,最终得到了判断一个特殊可交换 Thue系统是否完备化的线性时间复杂度算法 .     

含特殊类顾客有限容量的两级串联排队系统的平稳性态

在有限容量的两级串联排队系统的基础上,增加特殊类顾客的到达,研究模型M(x)/M/c→(M)/M/n/K.用矩阵几何分析的方法得出了系统模型的Q矩阵,运用拟生灭过程的方法给出了系统平稳的充要条件、平稳队长分布及其算法.     

有限交换群的自同构群阶

初等交换P-群的自同构群阶已经得到,对于其它情形则鲜有结果.文中得到了2类有限交换群的自同构群阶,并推广了P.Hall的一个相关结果.       

矩阵多项式组成的有限维交换代数

设A为域F上的n级矩阵,A的F上的多项式的全体关于矩阵的加法、数乘和乘法是以E为单位元的有限维交换代数.讨论了它的理想的性质,得到任意理想的表示形式,并用主理想刻画了它的结构.     

有限可换幺半群的一个商群

关于“群”有各种各样的定义,本文给出了有限幺半群成为群的一个条件。并对有限可换幺半群进行了讨论,通过对它的商集的研究,建立了有限可换幺半群与有限可换幺群之间的联系,从而揭示了有限可换幺半群的构造。     

半质环的交换性条件

本文改进了[1]中定理1,定理2及文[2]中的一个结果,并给出半质环另外一个交换性条件.     

有穷长半模偏序集上的一个定理

本文是对参考文献[1]第二章定理14证明的补充和改进。该定理乃指: 定理14.在任何上(或下)半模的有穷长的偏序集内,Jordan-Dedekind链条件成立。 文献[1]中,考虑上半模情形,谈到已知一个连接链:γ∶a=x_0相似文献   

Finite Dimensional Integrable Systems Related to Generalized Schr(o)dinger Equations

The binary nonlinearization method is applied to a 4×4 matrix eigenvalue problem. The typical system of the corresponding soliton hierarchy associated with this eigenvalue problem is the multi-component generalization of the nonlinear Schrodinger equation. With this method, Lax pairs and adjoint Lax pairs of the soliton hierarchy are reduced to two classes of finite dimensional Hamiltonian systems: a spatial finite dimensional Hamiltonian system and a hierarchy of temporal finite dimensional Hamiltonian systems. These finite dimensional Hamiltonian systems are commutative and Liouville integrable.     

关于有限网络的一个注记

相关文献研究了有限网络的下列颇具理论和应用价值的性质:考虑任意有限连通网络,其结点仅取"0"或"1"两种状态,开始时所有结点为"全0"状态,以后每次取定一个结点让它及其所有邻点全改变状态.该文利用数学建模成功地证明了一个与网络的大小和结构都无关的有趣结论:对任何网络经适当选取若干结点(按任意先后顺序依次)改变状态后,都能使网络从"全0"状态变为"全1"状态.且在此基础上进一步研究,给出连通网络选择点集(见定义1)的性质、树和单圈连通图选择点集的刻画、求任何连通网络全部选择点集的算法及其Matlab程序.