一个求强连通自动机的自同构群的多项式算法

在本文中,所谓自动机是指一个体系(?)=(S,∑),其中S为一个集合,其元素称为状态,∑为一个集合,其元素称为字母,并且对任何s∈S和σ∈∑,都有一个状态与之对应,并记作s~σ。∑的字母的有限序列称为字。称(?)是强连通的,如果对任何两个状态s,s′∈S都有∑上的字ω=σ_1σ_2…σ_i,使s~ω=s′,其中s~ω=(((s~(σ_1)~σ_2)…)~σ_t。称S到自身的一个1-1映     

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

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

O(n)时间有限Abel群同构检验算法

计算群论和复杂性理论中的一个重要问题是,有限群同构检验是可行的,还是NP完全的?这个问题迄今没有解决。C.Savage和陈溧分别得到一个O(n~2)时间的n阶Abel群同构检验算法。 本文得到,存在O(n)时间的n阶Abel群同构检验算法。即使使用对数成本的RAM,完成这样     

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

设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。     

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

设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)。     

局部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),使     

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

函数论学者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     

关于拟多项式映射零点分布的一个结果

设C~n是n维复空间。称P:C~n→C~n是拟多项式映射,如果P的每个分量P_i的每一项都具有形式αZ_l~(β_1)…Z_n~(β_n),其中α为复常数,Z_i为复变量,β_i为非负实数,并且每个P_i是有限个这样的项的和,对每个分量的每一项,考虑和式β_1+…+β_n。令α_i为第     

计算多项式GCD渐近快速算法的缺陷及其修正

令a_0和a_1是两个多项式,计算它们的最大公因式GCD,用DEG(a)表示多项式a的次数,设DEG(a_1)相似文献   

积木结构与多项式零点算法的计算复杂性问题

高度抽象性是现代数学的一大特点,但这也使人们对许多有意义的数学成果不能理解。《积木结构与多项式零点算法的计算复杂性问题》一文作者用较通俗的比喻对自己的工作及其背景、意义作了介绍。我们欢迎更多的数学工作者在可能情况下用类似方法向广大非数学的科技工作者介绍自己的重要成果。     

多项式全部零点的一族并行算法和区间算法

设f(z)是z∈C的N次代数多项式,对任意正整数p,令其中Yv是Bell多项式.则各个分量定义如下     

计算多项式零点的PL同伦算法的成本估计

零点计算问题。文献[1]提出一种分片线性(PL)同伦方法,简称KNA算法.因为引进一个扰动项,该方法不但计算零点,同时也给出零点的重数。然而,因为没有与多项式系数无关的误差估计,一直未能得出多项式     

关于线性变换完全环的极小单侧理想同构可扩张性的一个注记

§1.引言 本文中无特别声明的线性空间都指左空间。设Q_i是除环△_i上线性空间m_i的线性变换完全环(i=1,2)。许永华在讲义《本原环》的定理1.4.1中证明了这样的扩张定理:Ω_1与Ω_2的极小右理想间的环同构可唯一地扩张为Ω_1与Ω_2的环同构。本文的目的在于证明,对于极小左理想,不成立类似的定理。事实上,我们能证明,存在环同构极小左理想的两个线性变换     

多分有向图的同构因子分解——对Harary,Robinson,Wormald的一个关于有向图的同构因子分解猜想的证明

一个有向图D=(V,X)的一个同构因子分解是弧集合X的一个分划{X_1,X_2,…,X_i},使得昕有支撑子图(V,X_1),(V,X_2,),…,(V,X_i)都彼此同构。有向图D的每个非孤立的支撑子有向图被称为它的一个因子。若有向图D能分解为t个同构因子,     

矩阵乘法的一个最佳算法

一、引言 矩阵乘法是线性代数中常见的问题之一,许多数值计算问题都包含着矩阵乘法的计算。因此,降低矩阵乘法算法的时间复杂度问题,多年来一直引起算法研究者们的高度重视。 1969年,Strassen提出了一个时间复杂度为O(n~(log_2~7))的矩阵乘法算法,第一次突破了O(n~3)的界限,被誉为“在代数复杂性理论中最激动人心的结果”。以后,又出现了一系列新     

关于用车贝雪夫多项式做时间序列预报的几个问题

一、引言 在文献[1]中,我们提出了一种新的时间序列预报方法。此后,我们将这一方法用于新安江流域年降水趋势的预报和北京月降水量的预报。经预报与实况对照,说明这种方法效果较好。目前一些水文气象部门已在业务预报中应用了这一方法。 文献[1]提出的计算方法,系通过迭代运算完成。在该文中我们提出了迭代运算中应取理