双峰映射和Lorenz映射的复杂性研究

本文以形式语言和自动机理论为工具，研究一般的双峰映射和Ｌｏｒｅｎｚ映射生成的语言的复杂性，证明了语言为正规的充要条件是映射的揉序列均为终结周期．     

THE GRAMMATICAL COMPLEXITY AND SYMMETRY BREAKING OF SYMMETRICAL DYNAMICAL SYSTEMS

In this paper we discuss the grammatical complexity of dynamical systems,which satisfy antisymmetric condition and their iteratve interval can be divided into three monotone subintervals. A necessary and sufficient condition Jor the language determined by this system being regular language is proved.. Using the minimal DFA, symmetry breaking is analysed.     

双峰映射的一类最小有限自动机

本文研究了具有周期揉序列KS的双峰映射生成的形式语言￡(KS)，得到了接受语言￡(KS)的最小有限自动机，结出了计算￡(KS)的正规语言复杂性的公式．     

P元周期倒序广义对偶多维序列的复杂性分析

线性复杂度是度量密钥流序列的重要指标。在P元周期倒序单序列的对偶序列极小多项式性质的基础上,讨论了P元周期倒序广义对偶多维序列的极小多项式的性质,并明确给出P元周期倒序广义对偶多维序列与原多维序列之间的联合线性复杂度的关系式。这些结果很好地推动了密钥流多维序列的联合线性复杂度研究的发展。     

MXX和MARG中公式改名的复杂性

研究了判定问题“对于命题CNF公式F和H,是否存在一个变元(或文字)改名(?),使得(?)(F)=H?”的复杂性．对于极小不可满足公式的子类MAX和MARG,我们证明了:其变元改名和文字改名的复杂性等价于图同构问题GI．     

程序框图的自动结构化和结构复杂性度量

利用程序框图归约的概念,将程序框图分为强结构化、结构化和非结构化三类,以D—正则式和程序框图的符号关联矩阵为工具,提出了一种识别框图结构类别并自动生成强结构化框图的方法,给出了一种度量程序框图结构复杂性的尺度,并已用PASCAL语言实现.     

中立型泛函微分方程概周期解的存在性(Ⅱ)

本文用Liapunov泛函建立具有扰动的概周期中立型泛函微分方程概周期解的存在性。     

软件复杂度的自动分析方法

在分析结构化程度（或模块）复杂性度量方法基础上，提出一种软件复杂性度量的自动分析方法，并用该方法对一个实际的计算机管理信息系统进行了分析。     

r—循环系统及有关算法的计算复杂性

本文引进了对称r—循环阵的新概念,给出了r—循环阵和对称r—循环阵的一些性质,并利用FFT(快速富里叶变换),证明了有关算法的计算复杂性为O(nlog_2n),这里n为矩阵的阶数。     

A complexity analysis of the elementary cellular automaton of rule 122

S. Wolfram initiated the use of formal languages and automata theory in study of cellular automata (CAs). By means of extensive experiments with computer, he classified all CAs into four classes and conjectured that the limit languages of the third class of CAs, which produce chaotic aperiodic behavior, are not regular. Using symbolic dynamics and formal languages, we prove that the limit language of the elementary CA of rule 122 is neither regular nor context-free.     

算法复杂性定义的改进

算法复杂性的定义不能保证一个算法复杂性度量的唯一性。为了解决这个问题，本文给出了一个新的定义，并在新定义下，给出了计算复杂性度量的一个方法。     

原子布尔代数理论的计算复杂性

运用Ｅｈｒｅｎｆｅｕｃｈｔ Ｇａｍｅｓ理论给出原子布尔代数理论的一个判定过程及其复杂度,并说明这个过程在初等等价意义下是最优的。     

完备布尔代数理论的计算复杂性

运用改进的Ｅｈｅｒｎｆｅｕｃｈｔ ｇａｍｅｓ理论,适当定义了范数和囿函数,给出了无原子布尔代数理论的一个判定过程,利用这个结果,直接构造出完备布尔代数的判定过程,并且分析了它们的复杂度。     

Banach空间中概周期序列的谱

引入了Banach空间中与概周期函数类似的概周期序列谱与模的概念,并证明了概周期序列的谱与模有与概周期函数谱与模一样的性质.     

Feigenbaum函数方程的单峰偶解

Ｆｅｉｇｅｎｂａｕｍ函数方程解的存在及其性态的研究是动力系统普适性理论中的一个重要课题．本文对Ｆｅｉｇｅｎｂａｕｍ函数方程的单峰连续偶解进行了详尽的讨论，并给出连续解可成为Ｃｋ解的一个十分广泛的条件，还指出了文［６］的一个关键性错误．     

L~p空间中周期边值问题解的单调逼近

研究抽象空间微分方程周期解的存在性一直是比较困难的一个问题,Klaus Deimling于1985—1986年利用耗散性及紧性条件研究了这一问题解的存在性。本文从另外一个角度研究了赋范线性空间l~p中周期边值问题解的单调逼近,提出了计算解的具体方法。     

（m,n）型二重（R,r）—循环矩阵的有关算法及计算复杂性

利用快速傅里叶变换（FFT）技术,给出了计算（m,n)型二重（R,r)－循环矩阵的全部特征值和两个（m,n)型二重（R,r)－循环矩阵相乘的快速算法,证明了它们的计算复杂性均为O（mnlog2mn)。