一类交替的ω－有穷自动机

本文提出了一类交替的ω－有穷自动机（ω－ＵＡＦＡ），并采用了构造方法证明了ω－ＵＡＦＡ和简单的ω－ＵＡＦＡ在Ｃ＿１、Ｃ＿２、Ｃ＿５和Ｃ＿４接受条件下的等价性。

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

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

关于ω-有穷自动机的接受条件

关于ω－ 有穷自动要的接受条件的研究，旨在揭示ω－ 自动识别语言的能力以及对语言类作进一步的划分．到目前为止ω－ 自动机的接受条件已有六种，本文给出了一些新形式的接受条件并且研究了ω－ 有穷自动机在这些接受条件下接受ω－

一类交替的ω－有穷自动机和确定的ω－有穷自动机识别能力的等价性

本文提出了一类交替的ω－有穷自动机，即所有状态都是万能的交替的ω－有穷自动机（记为ω－ＵＡＦＡ），并采用了构造的方法证明了ω－ＵＡＦＡ和确定的ω－有穷自动机在四种接受条件下接受的ω－语言的等价性。

基于量子逻辑的几类有穷自动机之间的关系

根据初始状态和终止状态是否为分明的,非确定型量子有穷自动机可分为四类,确定型量子有穷自动机可分为三类.本文详细讨论了四类非确定型量子有穷自动机之间的关系以及三类确定型量子有穷自动机之间的关系,并且利用新的构造方法,证明了初态为分明的确定型量子有穷自动机与终态为分明的确定型量子有穷自动机是等价的.这些结论为实际应用中计算模型的合理选取提供了理论依据.

关于ω—有穷自动机的两个新的接受条件

至今被公开的ω有穷自动机的接受条件有６个即Ｃ１－Ｃ６，寻找新的接受条件和研究ω－有穷自动机关于新接受条件接受ω－语言能力是ω有穷自动机理论中的一个重要课题。本文定义了ω有穷自动机的两个新的接受条件Ｚ１和Ｚ２，并且研究了：（１）ω－Ｕ－ＮＦＡ关于Ｚｉ（ｉ＝１，２）接受ω－语文的能力。

关于ω－有穷自动机的接受条件

ω－有穷自动机的接受条件及ω－有穷自动机在各种接受条件接受ω－语言的能力的研究是ω－有穷自动机理论中的一个重要课题。至今被公开的ω－有穷自动机的接受条件有６种即Ｃ＿１Ｃ＿６．本文提出了其它６种与Ｃ＿１一Ｃ＿６形式上截然不同的接受条件，并且研究了ω－ＮＦＡ分别在，接受ω－语言的能力，得出了，分别与对应相等．

一种面向网络安全检测的高性能正则表达式匹配算法

目前进行正则表达式匹配的典型工具DFA和NFA都存在匹配效率和内存需求之间不可调和的矛盾,无法胜任网络安全检测中大规模正则表达式的匹配.为了解决这个问题,文中从网络安全检测的行为特点出发,结合DFA、NFA模型各自的特性,提出了一种基于猜测-验证的匹配方法.首先使用DFA对正则表达式中的部分子特征进行搜索,完成特征存在性的猜测;当猜测到有可能匹配某个特征后,再使用NFA进行验证.文中方法既充分利用了DFA的高效性,减少了对相对较慢的验证过程的调用,又借助NFA避免了内存消耗过于巨大.结果表明,该方法可以在大大减少内存需求的情况下,实现正则表达式的高效匹配.

一类ω—正则语言

ω—语言是由有穷字母表∑上的某些无穷串组成的集合。被所谓的ω—有穷自动机接受的ω—语言称为ω—正则语言。在[4]中作者曾从集合的角度给出—ω—语言为ω—正则语言的几个充分条件。在本文作者仍从集合的角度给出一个ω—语言为ω—正则语言的充分条件,即若—ω—凸语言L满足L=adh(pref(L))=pref(L)tail(L),则L是—ω—正则语言。从而,确定了ω—正则语言类的一个子类。

基于嵌套树的对等博弈应用研究

进行了软件系统性质验证研究。首先提出了用嵌套树表示软件程序的方法,以解决软件系统的抽象表示问题,该方法能在表示程序顺序结构的同时,更好地表示调用返回关系。然后定义了嵌套树上的μ-演算,以便将要验证的需求性质用公式表示,并把公式转化成非确定对等嵌套树自动机。最后将自动机与嵌套树结合,转化形成博弈图,并用对等博弈条件来判断博弈的输赢,这等同于检验验证公式是否在嵌套树上成立。相比直接验证,这种判定方法表达更为直观,且更有利于整个过程的自动化。研究表明,将嵌套树中的调用关系展开可形成概要标签树,嵌套树的对等博弈理论也可以应用到概要标签树中。