交替ω—有穷自动机接受ω—语言能力的研究

本文研究了交替ω－有穷自动机关于接受条件Ｚ１和Ｚ２接受ω＝语言的能力,并且与交替ω－有穷自动机关于另外接受条件接受ω－语言的能力进行了比较,从而得出了下面主要结果：ＡＣ１＝ＡＺ１＝Ａ６２Ｚ１＝Ａ＾ＳＺ２＝ＡＺ２。     

ω超线性语言

[1] 中定义了有穷转向的ω-pda 和ω-cfl,给出了它们的若干性质。本文讨论有穷转向的ω-cfl 的生成,定义ω超线性文法和ω超线性语言,证明ω超线性语言和有穷转向的ω-cfl是同一语言类。     

ω超线性语言类的封闭性质

本文给出以栈顶符号重复集接受的ω-cfl和有穷转向的ω-cfl的概念,而把空存储接受作为它的一个特例,证明以栈顶符号重复集接受和以状态重复集接受的ω-cfl(有穷转向的ω-cfl)是同一语言类.给出输入为ω字的f'转换器的概念,并讨论ω超线性语言对若干运算的封闭性质.     

有穷转向的ω前后文无关语言

本文以终止状态接受定义了k 次转向的PDA 以及k 次转向的CFL,讨论了它们和S.Ginsburg 以空存储接受定义的2k-1次转向的PDA 以及2k-1次转向的CFL 之间的关系,给出了k 次转向的PDA 以及相应语言的一些性质.对于ω输入的情况,定义了以状态重复集接受和以空存储接受的有穷转向的ω—PDA以及相应的ω—CFL,证明了这两种接受方式识别同一语言类,并给出了有穷转向的ω—CFL 的若干性质.     

带分隔符号＄的ω－语言理论──（Ⅱ）语言与ω－语言的统一

提出了一种新的语言──＄－ω－语言，把语言、ω－语言和＄－ω语言统一地讨论．特别对＄－ω正规语言进行了详细地讨论，得到了＄－ω正规语言的代数结构定理．提出了抽象正规表达式，得到了用同一个抽象正规表达式α表示正规语言Ｖ和ω－正规语言Ｖω的方法．     

时间ω-树自动机识别语言的一个条件

时间自动机被广泛用于实时系统验证和模型检验.为适应不同类型的系统验证需要,不少时间自动机的相关模型被提出.时间树自动机是这样的新模型之一.目前主要是针对时间树自动机识别的语言类及相关性质的研究.本文提出了时间树自动机识别语言的一个条件,并证明了结论的正确性.如果一个语言不能满足该条件,它一定不能被时间树自动机识别.这为证明一个具体语言不能被时间树自动机识别提供了思路.     

一种非确定型有穷自动机的极小化方法

自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言．确定型有穷状态自动机（DFA）极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机．而非确定型有穷状态自动机（NFA）极小化问题尚未找到有效算法．尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加．从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机．     

ω—自动机与扩大了的正规表达式

在提出扩大了正规表达式的概念的基础上，建立ω－自动机与扩大了的ω－正规表达工之间的１－１对应，并给出了２类不能构造出确定型ω－自动机的表达的（语言）。     

Lω-空间的Ⅰ型Lω-仿紧性

利用Lω-空间中的Lω-局部有限性质,引进了Lω-空间中的Ⅰ型Lω-仿紧性等概念,系统地研究了Ⅰ型Lω-仿紧性的基本性质,得到了Ⅰ型Lω-仿紧性在弱诱导条件下的一些等价条件.     

Lω-空间的ω-有限覆盖性质

研究了Lω-空间的ω-有限覆盖性质问题.利用Lω-空间的ω-远域和ω-覆盖等概念,系统讨论了ω-有限覆盖的特征性质,证明了Lω-空间的ω-有限覆盖性质具有拓扑不变性和闭遗传等性质.     

非确定模糊有穷自动机的ε-语言逼近

在max-*复合推理下引入了非确定模糊有穷自动机的概念,其中*是t-模运算。为了比较2个非确定模糊有穷自动机的行为,借助于[0, 1]上的一个实数ε,定义了2种ε-语言逼近,讨论了它们之间的关系。证明了非确定模糊有穷自动机和模糊有穷自动机之间是0-弱语言逼近的,即二者可以接受相同的模糊语言。此外,还讨论了2种ε-语言逼近的一些代数性质,特别地给出ε-语言逼近在并运算、*运算以及连接运算下的性质。最后,分析了ε-语言逼近的鲁棒性。     

汉字有穷自动机的优化及相关算法研究

在研究了汉字有穷自动机可以表示的语言基础上,引进了最小状态汉字有穷自动机和可区分状态的概念,并利用汉字有穷自动机间的等价性和可区分状态的性质,给出了一种最小化算法,实验证明,此算法优于最小化汉字有穷自动机算法.     

Lω-空间中的ωT11/2分离性

在Lω-空间中引入ωδ-闭集、ωT11/2分离性、分子网的ωδ-收敛性、理想的ωδ--收敛性、(ω,ω1)δ-连续性、几乎(ω,ω1)δ-连续性和强(ω,ω1)δ-连续性等概念.系统地研究了ωT11/2分离性的特征,给出了ωT11/2分离性的若干等价条件.证明了ωT11/2分离性是可遗传的、(ω,ω1)δ-同胚不变的、而且是R.Lowen意义下好的推广等重要性质.讨论了ωT11/2分离性、ωT11/2分离性和ωT2分离性之间的关系.     

正则表达式与有穷自动机等价性在Isabelle/HOL中的形式化

针对正则表达式和有穷自动机,在机器辅助定理证明系统Isabelle/HOL中进行了形式化描述。通过对语言、正则表达式、确定和不确定有穷自动机在Isabelle/HOL中建立模型,定义了它们之间的相互转换函数并证明了这些函数的正确性,从而验证了正则表达式和有穷自动机在描述能力上的等价性,即:在同一有限字母表下,对任意正则表达式,都存在一个有穷自动机,使得二者描述的语言相同;反之亦然。通过分析与证明,表明采用机器辅助定理证明系统,对计算理论传统核心领域之一的自动机理论进行分析和证明是可行的。     

Lω-空间的可数ω-紧性

研究了Lω-空间的可数ω-紧性。利用Hα-ω-开覆盖等概念,引进Lω-了空间的可数ω-紧性的概念,并证明了可数ω-紧性具有有限可和、对ω-闭子集遗传、被连续的广义Zadeh型函数所保持、L-good extension等许多性质。     

相对无挠模

讨论了相对于忠实平衡双模ω的相对无挠模的一些性质,给出了一个左或右Noether环是QF-环的一些等价条件, 并证明了当ω为广义倾斜双模时,ω-无挠模与 ω-1-合冲模以及ω-1-挠自由模均是等价的。研究了相对无挠模类的扩张封闭性。部分结果推广了关于经典的无挠模的结论。     

确定型有穷状态自动机的同态压缩

对于确定型有穷状态自动机(DFA),通过定义状态集上的等价关系≈Q,借助于等价关系,可以在平方时间内构造出接受相同语言的极小化自动机.本文在DFA之间引入同态关系,证明了同态压缩下DFA接受相同语言.     

偏序群的Dω－序扩展

讨论了偏序群的Ｄω－序扩展，得到了偏序群的偏序可扩展成为Ｄω－序的充要条件，以及每一偏序均可扩展成为Ｄω－序的条件，同时刻划了Ｄω－序群。     

有穷自动机状态极小化方法及正则语言判定优化

引入了等价性原则,定义等价关系的商集合∑*/～B,通过对商集合的有限性判断,来判定正则语言,大大简化了正则语言判定的步骤,并在有穷自动机的状态集上引入了等价关系,对等价状态进行压缩,构造出与其等价的最小有穷自动机,同时降低了有穷自动机状态的复杂性.     

Lω-空间的ω-强半连通性

在Lω-空间中定义了ω-强半开(闭)集,引入了一种新的连通性,称之为ω-强半连通性,给出ω-强半连通分支的定义,研究了它们的一些基本性质.结果表明这种连通性保持了一般拓扑中连通性的许多类似性质.