判断强连通自动机同构的一个多项式时间算法

众所周知,自动机的同构、图的同构等问题是多项式时间等价的(Booth,SIAM J.Comput,7(1978),3)。因此,讨论自动机的同构及其子问题是十分有意义的。最近,李慧陵给出了计算强连通自动机的自同构群的一个多项式时间算法。本文借助于此结果,在固定字母表的情况下,给出了判断两个强连通自动机是否同构的一个多项式时间算法。     

关于循环自动机若干问题的多项式时间算法

自动机A=(Q,Σ,δ)称为循环的。如果存在状态q_0∈Q,使得对于任何状态P∈Q,有x∈Σ~*,成立ε(q_0,x)=P;q_0称为A的一个生成元。本文中所指的自动机均为有限自动机。自动机A=(Q,Σ,δ)的一个自同态是一个映射ξ:Q→Q,满足(?)_a∈Σ,P∈Q(ξ(δ(P,a))=     

一类可解群的自同构

令R为有1的交换环,T(R)为由下定义的非Abelian群。生成元:x_(ij)(a),i相似文献   

椭圆曲线码的自同构群

设K是以F_q为常数域的单变量函数域,如果K是可离生成的且亏格为1的守恒域,则称K是椭圆函数域(定义见文献[1],p.190).我们总假设K中有一阶素除子且个数≥6,并用K(1)记作K中一阶素除子集合。在K(1)中取定一个元P_∞,那么我们可以在K(1)中定义一个加法,使K(1)是一个Abel群,P_∞是这个群中零元素,用〈K(1),⊕,P_∞〉记之,加法按如     

Toeplitz代数的自同构群

设B是C~n中单位球,S~(2n-1)是单位球面,Hardy空间H~2(S~(2n-1))上的Toeplitz算子如通常定义,C(S~(2n-1))是连续函数代数·记(?)(C(S~(2n-1))为{T_(?):(?)∈C(S~(2n-1))}生成的C~*-代数,Aut(E)为C~*-代数E的自同构群.刻划一个代数的自同构群,是算子代数中的基本问题之一.郭坤宇最近给出了代数(?)(H~∞)     

2维de Bruijn-Good图的自同构群

令m,n为正整数,M为任意集合,M上的2维(m,n)阶de Bruijn-Good图是一有向图,它的顶点集合V由M上的所有m×n阵组成,即     

自同构群的阶为p_q~2的有限群

设n为正整数,我们用C_n表示n阶循环群,D_(λn)表示2n阶二面体群(Dihedral Group)〈a,b|a~n=1=b~2,b~(-1)ab=a~(-1)〉,DC_((4n))表示4n阶双循环(Dicyclic)群〈a,b|a~(2n)=1,b~2=a~n,b~(-1)ab=a~(-1)〉。若素数     

一个有关三角多项式的不等式

设N是一个正整数,a_(M 1),a_(M 2),…,a_(M N)是N个任意的复数。现定义S(x)=sum from n=M 1 to M N a_ne(nx),(1)其中e(t)=e~(2πit)。又设x_1,x_2,…,x_R是R个实数,对r≠s,‖x_r-x_s‖≥δ.(2)这里‖θ‖表示θ到最近整数的距离,且0<δ<1/2。     

半局部环上的二维线性群的自同构

体(域)上的二维线性群的自同构已由华罗庚、万哲先(1963)给出。Reiner、Landin、Dull等人曾对某些欧氏环及一般整区上的二维线性群的自同构形式做过研究。王仁发最近决定出局部环上的二维线性群的自同构。本文在此基础上,给出了半局部环上二维线性群的自同构。     

四元整数环上二维线性群的自同构

设K是有理四元数体,即形为a bi cj dk(其中a,b,c,d均为有理数)的四元数全体。令R={(1/2)(a bi cj dk)∈K|a,b,c,d全为奇数或全为偶数},则R叫四元整     

多项式映射可逆性的一个判则

设F是特征为零的域,f_i∈F[x_1,…,x_n],1≤i≤n。若多项式映射φ=(f_1,…,f_n)-F~(?)→F~n (x_1,…,x_n)(?)(f_1(x_1,…,x_n),…,f_n(x_1,…,x_n))可逆,易知其Jacobi行列式J(f_1,…,f_n)=det((?)f_i/(?)x_i)必为F中非零元。这一命题之逆,就是著名的Jacobi猜想。从Keller正式提出这一问题起,迄今已近五十年,仍未得到解决。     

关于正则局部连通空间的一个结果

文[1]将“连续开映射保持局部连通性”这一古典结果推广为“几乎开的连续满映射保持局部连通性”。文[2]继续将之改进为“设X是局部连通     

极小n棱连通图的一个定理

D. R. Lick(J. Reine Angew. Math., 1972)首先证明:极小n棱连通图的最小度点数为n。W。Mader(Math。Ann。,1971)推广了上述结论,证明:极小n棱连通图至少有n 1个度n的点。本文推广了Mader的定理,证明了:     

Bernstein多项式取正值的一个充要条件

设f(x)是定义在[0,1]上的一个函数,由f所确定的n次Bernstein多项式是指     

关于Kuhn多项式求根算法的效率

按照Smale一种算法称作是良好的,如果计算复系数多项式一个根的成本,随多项式阶数增加不是指数式的。对于形如f(z)=x~z c_1z~(a-1) … c_m,所有|c_k|<1的多项式,Smale证明了Newton方法算一个根的成本按[100(n 2)]~9/μ~7增加,这里μ是允许论断失败的概率,0<μ<1(BulletinAMS,4(1981),1—36)。     

四元整数环上二维射影线性群的自同构

设K是有理四元数体,它含有四元整数环R={(a bi cj dk)/2|a,b,c,d同为奇数或同为偶数}作为子环,而R是非交换欧几里得环,由文献[1]知,R的乘法可逆元组成之群U={±1,±i,±j,±k,(±1±i±j±k)/2},U的换位子群H={±1,±i,±j,±k},     

2是非单位的局部环上二维线性群的自同构

2是单位的局部环上,二维线性群的自同构已有些结果。然而,2是非单位的情形,除2是特征外,还未见较为一般性结果。本文假定剩余域不是F_2的情形下,得出它的自同构形式。     

模型论对多项式理论的一个应用

函数论学者M.Marden在Math.Reviews,47(1974),第8827页评介中说,A.Sudbery (Bull.London Math.Soc., 5(1973),13—17)证明了:在复数域中,若p(z)为一n次多项式且至少有两个不同的根,则乘积P(z)=p(z)p'(z)…P~((n))(z)至少有n 1个不同的根,Marden并引述了Sudbery     

局部S-闭空间极不连通的一个充要条件

本文给出局部s-闭空间极不连通的一个必要与充分条件。这个结果不仅统一推广了T.Noiri(Proc.Amer.Math.Soc.,79(1980),327—329)主要的两条定理,而且改进了王国俊(数学学报,24(1981),55—63)的定理:“S-闭的P_Σ型拓扑空间是极不连通的。”定义(Nolri)拓扑空间X的子集W称为相对于XS-闭的,如果对X中覆盖W的任一半开集族{Ar|r∈Γ),存在有限子族{Ar_i|i=1,…,n),使